<html>

<head>
	<meta http-equiv="content-type" content="text/html; charset=utf-8" />
	<title>i5ting_ztree_toc:系统</title>
	<link href="./github-bf51422f4bb36427d391e4b75a1daa083c2d840e.css" media="all" rel="stylesheet"
		type="text/css" />
	<link href="./github2-d731afd4f624c99a4b19ad69f3083cd6d02b81d5.css" media="all" rel="stylesheet"
		type="text/css" />
</head>

<body>
		<div id='readme' style='width:95vw;'>
			<article class='markdown-body'>
				<h1 id="-">计算机系统概述</h1>
				<h2 id="-">硬件结构</h2>
				<h3 id="cpu-">CPU运行过程</h3>
				<h4 id="-">冯若依曼模型</h4>
				<ul>
					<li>运算器、控制器（在中央处理器CPU中）</li>
					<li>存储器，就是内存</li>
					<li>输入设备、输出设备（外接设备）</li>
				</ul>
				<p>1<strong>中央处理器CPU</strong></p>
				<ul>
					<li>32位CPU一次可以计算4个字节</li>
					<li>64位CPU一次可以计算8个字节</li>
				</ul>
				<p>CPU内部还有一些组件，常见的有<strong>寄存器</strong>、<strong>控制单元</strong>(控制CPU工作)、<strong>逻辑运算单元</strong>(复杂计算)</p>
				<p>常见寄存器种类：</p>
				<ul>
					<li><strong>通用寄存器</strong>，用来存放需要进行运算的数据，比如需要进行加和运算的两个数据。</li>
					<li><strong>程序计数器</strong>，用来存储 CPU
						要执行下一条指令「所在的内存地址」，注意不是存储了下一条要执行的指令，此时指令还在内存中，程序计数器只是存储了下一条指令「的地址」。</li>
					<li><strong>指令寄存器</strong>，用来存放当前正在执行的指令，也就是指令本身，指令被执行完成之前，指令都存储在这里。</li>
				</ul>
				<p><strong>总线</strong>，用于 CPU 和内存以及其他设备之间的通信</p>
				<ul>
					<li><strong>地址总线</strong>，用于指定 CPU 将要操作的内存地址；（指定内存地址）</li>
					<li><strong>数据总线</strong>，用于读写内存的数据；（控制读写命令）</li>
					<li><strong>控制总线</strong>，用于发送和接收信号，比如中断、设备复位等信号，CPU 收到信号后自然进行响应，这时也需要控制总线；（传输数据）</li>
				</ul>
				<p><strong>输入、输出设备</strong></p>
				<p>输入设备向计算机输入数据，计算机经过计算后，把数据输出给输出设备。期间，如果输入设备是键盘，按下按键时是需要和 CPU 进行交互的，这时就需要用到控制总线了。</p>
				<p><strong>线路位宽与CPU位宽</strong></p>
				<p>CPU 的位宽最好不要小于线路位宽，如果用 32 位 CPU 去加和两个 64 位大小的数字，就需要把这 2 个 64 位的数字分成 2 个低位 32 位数字和 2 个高位 32
					位数字来计算，先加个两个低位的 32 位数字，算出进位，然后加和两个高位的 32 位数字，最后再加上进位，就能算出结果了，可以发现 32 位 CPU 并不能一次性计算出加和两个 64
					位数字的结果。<strong>如果计算的数额不超过 32 位数字的情况下，32 位和 64 位 CPU 之间没什么区别的，只有当计算超过 32 位数字的情况下，64
						位的优势才能体现出来</strong>。</p>
				<p><strong>64位相比32位的优势</strong></p>
				<ul>
					<li>64 位 CPU 可以一次计算超过 32 位的数字，而 32 位 CPU 如果要计算超过 32
						位的数字，要分多步骤进行计算，效率就没那么高，但是大部分应用程序很少会计算那么大的数字，所以<strong>只有运算大数字的时候，64 位 CPU 的优势才能体现出来，否则和 32 位 CPU
							的计算性能相差不大</strong>。</li>
					<li>通常来说 <strong>64 位 CPU 的地址总线是 48 位，而 32 位 CPU 的地址总线是 32 位</strong>，所以 64 位 CPU
						可以<strong>寻址更大的物理内存空间</strong>。如果一个 32 位 CPU 的地址总线是 32 位，那么该 CPU 最大寻址能力是 4G，即使你加了 8G
						大小的物理内存，也还是只能寻址到 4G 大小的地址，而如果一个 64 位 CPU 的地址总线是 48 位，那么该 CPU 最大寻址能力是 <code>2^48</code>，远超于 32 位
						CPU 最大寻址能力。</li>
				</ul>
				<p>如果 32 位指令在 64 位机器上执行，需要一套兼容机制，就可以做到兼容运行了。但是<strong>如果 64 位指令在 32 位机器上执行，就比较困难了，因为 32 位的寄存器存不下 64
						位的指令</strong>；</p>
				<h4 id="-"><strong>程序执行的基本过程</strong></h4>
				<ul>
					<li>第一步，CPU 读取「程序计数器」的值，这个值是指令的内存地址，然后 CPU
						的「控制单元」操作「地址总线」指定需要访问的内存地址，接着通知内存设备准备数据，数据准备好后通过「数据总线」将指令数据传给 CPU，CPU
						收到内存传来的数据后，将这个指令数据存入到「指令寄存器」。</li>
					<li>第二步，「程序计数器」的值自增，表示指向下一条指令。这个自增的大小，由 CPU 的位宽决定，比如 32 位的 CPU，指令是 4 个字节，需要 4 个内存地址存放，因此「程序计数器」的值会自增
						4；</li>
					<li>第三步，CPU 分析「指令寄存器」中的指令，确定指令的类型和参数，如果是计算类型的指令，就把指令交给「逻辑运算单元」运算；如果是存储类型的指令，则交由「控制单元」执行；</li>
				</ul>
				<p>简单总结一下就是，一个程序执行的时候，CPU 会根据程序计数器里的内存地址，从内存里面把需要执行的指令读取到指令寄存器里面执行，然后根据指令长度自增，开始顺序读取下一条指令。</p>
				<h4 id="a-1-2-"><strong>a=1+2执行具体过程</strong></h4>
				<p>程序编译过程中，编译器通过分析代码，发现 1 和 2 是数据，于是程序运行时，内存会有个专门的区域来存放这些数据，这个区域就是「数据段」。</p>
				<ul>
					<li>数据 1 被存放到 0x200 位置；</li>
					<li>数据 2 被存放到 0x204 位置；</li>
				</ul>
				<p>编译器会把 <code>a = 1 + 2</code> 翻译成 4 条指令，存放到正文段中。如图，这 4 条指令被存放到了 0x100 ~ 0x10c 的区域中：</p>
				<ul>
					<li>0x100 的内容是 <code>load</code> 指令将 0x200 地址中的数据 1 装入到寄存器 <code>R0</code>；</li>
					<li>0x104 的内容是 <code>load</code> 指令将 0x204 地址中的数据 2 装入到寄存器 <code>R1</code>；</li>
					<li>0x108 的内容是 <code>add</code> 指令将寄存器 <code>R0</code> 和 <code>R1</code> 的数据相加，并把结果存放到寄存器
						<code>R2</code>；</li>
					<li>0x10c 的内容是 <code>store</code> 指令将寄存器 <code>R2</code> 中的数据存回数据段中的 0x208 地址中，这个地址也就是变量
						<code>a</code> 内存中的地址；</li>
				</ul>
				<p>编译完成后，具体执行程序的时候，程序计数器会被设置为 0x100 地址，然后依次执行这 4 条指令。</p>
				<h4 id="-">怎么让程序跑的更快</h4>
				<p>程序的CPU执行时间 = CPU时钟周期数 X 时钟周期时间 = 指令数 X CPI(每条指令的平均时钟周期数) X 时钟周期时间</p>
				<ul>
					<li>提高CPU主频（缩短时钟周期时间）</li>
					<li>减少程序所需的CPU时钟周期数量</li>
					<li>减少指令数</li>
				</ul>
				<h3 id="-">内存与磁盘</h3>
				<p><strong>存储结构</strong>，越上面处理越快，能耗越高，材料成本越贵，容量越小</p>
				<ul>
					<li>CPU<ul>
							<li>寄存器，正在处理的</li>
							<li>CPU Cache，静态随机存储器<ul>
									<li>L1-Cache，指令缓存与数据缓存，每个CPU核心独享</li>
									<li>L2-Cache，高速缓存，每个CPU核心独享</li>
									<li>L3-Cache，多个CPU核心共享</li>
								</ul>
							</li>
						</ul>
					</li>
					<li>内存，动态随机存取存储器。密度更高，功耗更低</li>
					<li>SSD/HDD 硬盘</li>
				</ul>
				<p>CPU Cache 的数据是从内存加载过来的，写回数据的时候也只写回到内存，CPU Cache 不会直接把数据写到硬盘，也不会直接从硬盘加载数据，而是先加载到内存，再从内存加载到 CPU Cache
					中。<strong>每个存储器只和相邻的一层存储器设备打交道，并且存储设备为了追求更快的速度，所需的材料成本必然也是更高，也正因为成本太高，所以 CPU 内部的寄存器、L1\L2\L3 Cache
						只好用较小的容量，相反内存、硬盘则可用更大的容量，这就我们今天所说的存储器层次结构</strong>。</p>
				<p>访村顺序，看寄存器中有没有，没有L1，L2，L3，然后内存</p>
				<h3 id="-cpu-">如何写出让CPU跑的更快的代码</h3>
				<ul>
					<li>提升<strong>数据缓存</strong>的命中率，遇见遍历数组情况，按照<strong>内存布局顺序访问</strong>，可以有效利用CPU Cache 带来的好处。</li>
					<li>提升<strong>指令缓存</strong>的命中率，<strong>有规律的条件分支语句</strong>能够让 CPU 的分支预测器发挥作用，进一步提高执行的效率</li>
					<li>提升<strong>多核CPU的缓存命中率</strong>，把<strong>线程绑定在某一个 CPU 核心上</strong></li>
				</ul>
				<h3 id="cpu-">CPU缓存一致性</h3>
				<p><strong>数据写入内存</strong></p>
				<ul>
					<li>写直达，把数据同时写入内存和Cache<ul>
							<li>写入前先判断数据是否已经在CPU Cache中<ul>
									<li>如果已经在Cache，先将数据更新到Cache，在写入内存</li>
									<li>如果没有在Cache，直接把数据更新到内存</li>
								</ul>
							</li>
						</ul>
					</li>
					<li>写回，当发生写操作时，新的数据仅仅被写入 Cache Block 里，只有<strong>当修改过的 Cache Block「被替换」</strong>时才需要写到内存中<ul>
							<li>优点，如果我们大量的操作都能够命中缓存，那么大部分时间里 CPU 都不需要读写内存，自然性能相比写直达会高很多。</li>
						</ul>
					</li>
				</ul>
				<p><strong>同步不同内核的缓存数据</strong></p>
				<ul>
					<li>第一点，某个 CPU 核心里的 Cache 数据更新时，必须要传播到其他核心的 Cache，这个称为<strong>写传播</strong>；</li>
					<li>第二点，某个 CPU 核心里对数据的操作顺序，必须在其他核心看起来顺序是一样的，这个称为<strong>事务的串行化</strong></li>
				</ul>
				<p><strong>写传播技术实现--总线嗅探</strong></p>
				<p>CPU 需要每时每刻监听总线上的一切活动，但是不管别的核心的 Cache 是否缓存相同的数据，都需要发出一个广播事件</p>
				<p><strong>事务串行化技术实现--MESI协议</strong></p>
				<p>MESI 协议，是已修改、独占、共享、已失效这四个状态的英文缩写的组合。整个 MSI 状态的变更，则是根据来自本地 CPU 核心的请求，或者来自其他 CPU
					核心通过总线传输过来的请求，从而构成一个流动的状态机。另外，对于在「已修改」或者「独占」状态的 Cache Line，修改更新其数据不需要发送广播给其他 CPU 核心。</p>
				<h3 id="cpu-">CPU是如何执行任务的</h3>
				<p><strong>CPU如何读写数据</strong></p>
				<p>CPU 从内存中读取数据到 Cache 的时候，并不是一个字节一个字节读取，而是一块一块的方式来读取数据的，这一块一块的数据被称为 CPU Cache Line（缓存块），所以 <strong>CPU
						Cache Line 是 CPU 从内存读取数据到 Cache 的单位</strong>。</p>
				<p>对数组的加载， CPU 就会加载数组里面连续的多个数据到 Cache 里，因此我们应该按照物理内存地址分布的顺序去访问元素</p>
				<p>在我们不使用数组，而是使用单独的变量的时候，则会有 <strong>Cache 伪共享</strong>的问题（因为多个线程同时读写同一个 Cache Line 的不同变量时，而导致 CPU Cache
					失效的现象）</p>
				<p>避免伪共享的方法</p>
				<ul>
					<li>针对在同一个 Cache Line 中的共享的数据，如果在多核之间竞争比较严重，为了防止伪共享现象的发生，可以采用上面的宏定义使得变量在 Cache Line
						里是对齐的。（用空间换时间的思想，浪费一部分 Cache 空间，从而换来性能的提升）</li>
					<li>字节填充 + 继承</li>
				</ul>
				<p><strong>CPU如何选择线程</strong></p>
				<ul>
					<li>在 Linux 内核中，进程和线程都是用 <code>task_struct</code> 结构体表示的，区别在于线程的 task_struct
						结构体里部分资源是共享了进程已创建的资源，比如内存地址空间、代码段、文件描述符等，所以 Linux
						中的线程也被称为轻量级进程，因为线程的<code>task_struct</code>相比进程的<code>task_struct</code> 承载的
						资源比较少，因此以「轻」得名；Linux 内核里的调度器，调度的对象就是 <code>task_struct</code></li>
					<li>在 Linux 系统中，根据任务的优先级以及响应要求，主要分为两种，其中优先级的数值越小，优先级越高：<ul>
							<li>实时任务，对系统的响应时间要求很高，也就是要尽可能快的执行实时任务，优先级在 <code>0~99</code> 范围内的就算实时任务；</li>
							<li>普通任务，响应时间没有很高的要求，优先级在 <code>100~139</code> 范围内都是普通任务级别</li>
						</ul>
					</li>
					<li>系统中需要运行的多线程数一般都会大于 CPU 核心，这样就会导致线程排队等待 CPU，这可能会产生一定的延时，如果我们的任务对延时容忍度很低，则可以通过一些人为手段干预 Linux
						的默认调度策略和优先级</li>
				</ul>
				<h3 id="-0-1-0-2-0-3-">为什么0.1+0.2不等于0.3？</h3>
				<p>十进制数转二进制采用的是除 2 取余，十进制小数使用的是乘2取整法</p>
				<p>负数，符号位置为1，同时取反+1。补码的方式是为了统一和正数的加减操作</p>
				<p>不是的，0.1 和 0.2 这两个数字用二进制表达会是一个一直循环的二进制数，比如 0.1 的二进制表示为 0.0 0011 0011 0011… （0011 无限循环)，对于计算机而言，0.1
					无法精确表达，这是浮点数计算造成精度损失的根源。所以计算机里只能采用近似数的方式来保存，那两个近似数相加，得到的必然也是一个近似数。</p>
				<h2 id="-">内核——<strong>应用连接硬件设备的桥梁</strong></h2>
				<h3 id="-">内核介绍</h3>
				<p><strong>内核的架构</strong>：</p>
				<ul>
					<li>宏内核，包含系统内核的所有模块，整个内核像一个完整的程序；</li>
					<li>微内核，只保留最基本的能力，一些模块和服务则由用户态管理；</li>
					<li>混合内核，是宏内核和微内核的结合体，内核中抽象出了微内核的概念，也就是内核中会有一个小型的内核，其他模块就在这个基础上搭建，整个内核是个完整的程序；</li>
				</ul>
				<p><strong>内核4个基本能力</strong>：</p>
				<ul>
					<li><strong>进程调度</strong>，管理进程、线程、决定哪个进程、线程使用CPU。</li>
					<li><strong>内存管理</strong>，决定内存分配和回收。</li>
					<li><strong>硬件通信</strong>，管理硬件设备，为进程与硬件设备之间提供通信能力。</li>
					<li><strong>提供系统调用</strong>，作为用户程序与操作系统之间的接口，使得应用程序能够运行更高权限运行的服务。</li>
				</ul>
				<p>内核具有很高的权限，可以控制 CPU、内存、硬盘等硬件，而应用程序具有的权限很小，因此大多数操作系统，把内存分成了两个区域：</p>
				<ul>
					<li>内核空间，这个内存空间只有内核程序可以访问。当程序使内核空间时，程序则在<strong>内核态</strong>执行。</li>
					<li>用户空间，这个内存空间专门给应用程序使用。当程序使用用户空间时，我们常说该程序在<strong>用户态</strong>执行。</li>
				</ul>
				<p><strong>系统调用过程如下：</strong></p>
				<p><img src="https://cdn.xiaolincoding.com/gh/xiaolincoder/ImageHost4@main/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/%E5%86%85%E6%A0%B8/systemcall.png"
						style="zoom:67%;" /></p>
				<p><strong>内核程序执行在内核态，用户程序执行在用户态。</strong>当应用程序使用系统调用时，会产生一个中断。发生中断后， CPU
					会中断当前在执行的用户程序(执行陷入指令,后立即引发一个内中断，从而CPU进入核心态)，转而跳转到中断处理程序，也就是开始执行内核程序。内核处理完后，主动触发中断，把 CPU
					执行权限交回给用户程序，回到用户态继续工作。（注，内中断，中断来自CPU内部）</p>
				<h3 id="linux-windows">Linux与Windows</h3>
				<h4 id="linux-">Linux，宏内核</h4>
				<p>设计理念：</p>
				<ul>
					<li><em>Multitask</em>，多任务，代表Linux是一个多任务的操作系统。</li>
					<li><em>SMP</em>，对称多处理，代表每个CPU的地位是相等的，对资源的使用权限也是相同的，多个CPU共享同一个内存，每个CPU都可以访问完整的内存和硬件资源。</li>
					<li><em>ELF</em>，可执行文件链接格式，Linux操作系统中可执行文件的存储格式。</li>
					<li><em>Monolithic
							Kernel</em>，宏内核，包含进程调度、内存管理、文件系统、设备驱动等，都运行在内核态。<strong>同时Linux也实现了动态加载内核模块功能</strong>。</li>
				</ul>
				<p>动态加载内核模块功能，例如大部分设备驱动是以可加载模块的形式存在的，与内核其他模块解藕，让驱动开发和驱动加载更为方便、灵活。</p>
				<h4 id="windows-">Windows，混合内核</h4>
				<p>Windows 和 Linux 一样，同样支持 Multitask 和 SMP，但不同的是，<strong>Window 的内核设计是混合型内核</strong>，在上图你可以看到内核中有一个
					<em>MicroKernel</em> 模块，这个就是最小版本的内核，而整个内核实现是一个完整的程序，含有非常多模块。</p>
				<p>Windows 的可执行文件格式叫
					PE，称为<strong>可移植执行文件</strong>，扩展名通常是<code>.exe</code>、<code>.dll</code>、<code>.sys</code>等。</p>
				<h2 id="-a-">键盘敲入A字母时，操作系统期间发生了什么？</h2>
				<p>那当用户输入了键盘字符，<strong>键盘控制器</strong>就会产生扫描码数据，并将其缓冲在键盘控制器的寄存器中，紧接着键盘控制器通过总线给 CPU
					发送<strong>中断请求</strong>。</p>
				<p>CPU 收到中断请求后，操作系统会<strong>保存被中断进程的 CPU 上下文</strong>，然后调用键盘的<strong>中断处理程序</strong>。</p>
				<p>键盘的中断处理程序是在<strong>键盘驱动程序</strong>初始化时注册的，那键盘<strong>中断处理函数</strong>的功能就是从键盘控制器的寄存器的缓冲区读取扫描码，再根据扫描码找到用户在键盘输入的字符，如果输入的字符是显示字符，那就会把扫描码翻译成对应显示字符的
					ASCII 码，比如用户在键盘输入的是字母 A，是显示字符，于是就会把扫描码翻译成 A 字符的 ASCII 码。</p>
				<p>得到了显示字符的 ASCII 码后，就会把 ASCII
					码放到「读缓冲区队列」，接下来就是要把显示字符显示屏幕了，显示设备的驱动程序会定时从「读缓冲区队列」读取数据放到「写缓冲区队列」，最后把「写缓冲区队列」的数据一个一个写入到显示设备的控制器的寄存器中的数据缓冲区，最后将这些数据显示在屏幕里。
				</p>
				<p>显示出结果后，<strong>恢复被中断进程的上下文</strong>。</p>
				<h1 id="-">进程管理</h1>
				<h2 id="-">进程</h2>
				<h3 id="-">进程的基本知识</h3>
				<p>进程(<strong>资源分配的单位)</strong>：代码通过编译后生成二进制可执行文件，运行可执行文件后，它会被装载入内存，然后CPU执行程序中的每个指令，<strong>这个运行中的程序。就被称为进程。</strong>进程切换前，必须记录下当前进程中运行的状态信息，以备下次切换回来的时候可以恢复执行。（进程上下文切换）
				</p>
				<h4 id="-">进程的控制结构</h4>
				<p><strong>PCB是进程存在的唯一标识</strong>。通常是通过<strong>链表</strong>的方式组织，把具有相同状态的进程连接在一起，组成各种队列。除了链表的方式，还有<strong>索引</strong>方式。但是，在面临进程创建、销毁时，链表对于插入和删除操作更加灵活，所以一般使用链表。
				</p>
				<p>具体包含信息：</p>
				<ul>
					<li><strong>进程描述信息：</strong>
						<ul>
							<li>进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符；</li>
							<li>用户标识符：进程归属的用户，用户标识符主要为共享和保护服务；</li>
						</ul>
					</li>
					<li><strong>进程控制和管理信息：</strong>
						<ul>
							<li>进程当前状态，如 new、ready、running、waiting 或 blocked 等；</li>
							<li>进程优先级：进程抢占 CPU 时的优先级；</li>
						</ul>
					</li>
					<li><strong>资源分配清单：</strong>
						<ul>
							<li>有关内存地址空间或虚拟地址空间的信息，所打开文件的列表和所使用的 I/O 设备信息。</li>
						</ul>
					</li>
					<li><strong>CPU 相关信息：</strong>
						<ul>
							<li>CPU 中各个寄存器的值，当进程被切换时，CPU 的状态信息都会被保存在相应的 PCB 中，以便进程重新执行时，能从断点处继续执行。</li>
						</ul>
					</li>
				</ul>
				<h4 id="-">进程控制</h4>
				<ul>
					<li>
						<p>创建进程，操作系统允许一个进程创建另一个进程，而且允许子进程继承父进程所拥有的资源。</p>
						<ul>
							<li>申请一个空白的 PCB，并向 PCB 中填写一些控制和管理进程的信息，比如进程的唯一标识等；</li>
							<li>为该进程分配运行时所必需的资源，比如内存资源；</li>
							<li>将 PCB 插入到就绪队列，等待被调度运行；</li>
						</ul>
					</li>
					<li>
						<p>终止进程，有 3 种终止方式：正常结束、异常结束以及外界干预（信号 <code>kill</code>
							掉）。<strong>当子进程被终止，其继承资源还给父进程，而当父进程被终止，父进程的子进程变为孤儿进程，会被1号进程收集，同时1号进程对他们完成状态收集工作</strong>。
						</p>
						<ul>
							<li>查找需要终止的进程的 PCB；</li>
							<li>如果处于执行状态，则立即终止该进程的执行，然后将 CPU 资源分配给其他进程；</li>
							<li>如果其还有子进程，则应将该进程的子进程交给 1 号进程接管；</li>
							<li>将该进程所拥有的全部资源都归还给操作系统；</li>
							<li>将其从 PCB 所在队列中删除；</li>
						</ul>
					</li>
					<li>阻塞进程，一旦被阻塞，只能由另一个进程唤醒。<ul>
							<li>找到将要被阻塞进程标识号对应的 PCB；</li>
							<li>如果该进程为运行状态，则保护其现场，将其状态转为阻塞状态，停止运行；</li>
							<li>将该 PCB 插入到阻塞队列中去；</li>
						</ul>
					</li>
					<li>唤醒进程<ul>
							<li>在该事件的阻塞队列中找到相应进程的 PCB；</li>
							<li>将其从阻塞队列中移出，并置其状态为就绪状态；</li>
							<li>把该 PCB 插入到就绪队列中，等待调度程序调度；</li>
						</ul>
					</li>
				</ul>
				<h4 id="-">进程的上下文切换</h4>
				<p>各个进程之间是共享 CPU 资源的，进程之间需要切换，让不同的进程可以在 CPU 执行，当<strong>一个进程切换到另一个进程运行，称为进程的上下文切换</strong>。</p>
				<p><strong>进程的上下文切换不仅包含了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的资源。</strong>(进程本身+运行环境)</p>
				<p>进程上下文切换场景：</p>
				<ul>
					<li>为了保证所有进程可以得到公平调度，CPU
						时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，进程就从运行状态变为就绪状态，系统从就绪队列选择另外一个进程运行；</li>
					<li>进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行；</li>
					<li>当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度；</li>
					<li>当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行；</li>
					<li>发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序；</li>
				</ul>
				<h3 id="-">进程状态</h3>
				<p>一个进程活动中至少具备三种基本状态，<strong>运行态，就绪态，阻塞态</strong>。</p>
				<ul>
					<li>运行状态（<em>Running</em>）：该时刻进程占用
						CPU。当时间片用完，转化为就绪状态。当进程请求某个事件且必须等待时，转换为阻塞态。当进程主动通过sleep睡眠函数将自己主动挂起或者资源不足、更高优先级进程运行时，转换为挂起态。</li>
					<li>就绪状态（<em>Ready</em>）：可运行，<strong>由于其他进程处于运行状态而暂时停止运行</strong>。当进程被操作系统的进程调度器选中，转化为运行态。</li>
					<li>
						<p>阻塞状态（<em>Blocked</em>）：该进程正在等待某一事件发生（如等待输入/输出操作的完成）而暂时停止运行，这时，即使给它CPU控制权，它也无法运行。当等待事件完成，转化为就绪态。
						</p>
					</li>
					<li>
						<p>创建状态（<em>new</em>）：进程正在被创建时的状态；当进程被创建完成并初始化后，一切准备就绪，便转化为就绪态。</p>
					</li>
					<li>结束状态（<em>Exit</em>）：进程正在从系统中消失时的状态；</li>
					<li>挂起状态 ：为了防止大量处于阻塞状态的进程占用物理内存，所以把阻塞状态的进程物理内存换出硬盘，等需要运行时，从从硬盘换入物理内存。描述进程没有占用实际的物理内存空间。<ul>
							<li>阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；</li>
							<li>就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行</li>
						</ul>
					</li>
				</ul>
				<p><img src="https://cdn.xiaolincoding.com/gh/xiaolincoder/ImageHost/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/%E8%BF%9B%E7%A8%8B%E5%92%8C%E7%BA%BF%E7%A8%8B/10-%E8%BF%9B%E7%A8%8B%E4%B8%83%E4%B8%AD%E7%8A%B6%E6%80%81.jpg"
						style="zoom:70%;" /></p>
				<p>注：</p>
				<ul>
					<li>只有就绪态和运行态可以相互转化（不包括挂起）。</li>
					<li>阻塞态是缺少需要的资源从运行态转换而来，但该资源不包括CPU时间(时间片)，缺少CPU时间会从运行态转化就绪态。</li>
					<li>导致进程挂起的原因不只是因为进程所使用的内存空间不在物理内存，还包括如下情况：<ul>
							<li>通过 sleep 让进程间歇性挂起，其工作原理是设置一个定时器，到期后唤醒进程。</li>
							<li>用户希望挂起一个程序的执行，比如在 Linux 中用 <code>Ctrl+Z</code> 挂起进程；</li>
						</ul>
					</li>
				</ul>
				<h3 id="-">进程调度</h3>
				<p>在进程的生命周期中，当进程从一个运行状态到另外一状态变化的时候，其实会触发一次调度。</p>
				<ul>
					<li>进程从运行态 <em>-&gt;</em> 阻塞态，为非抢占式调度。</li>
					<li>运行态 <em>-&gt;</em> 就绪态，为抢占式调度。时间片到了。</li>
					<li>运行态 <em>-&gt;</em> 终止态，为非抢占式调度。</li>
					<li>
						<p>阻塞(等待)状态 <em>-&gt;</em>
							就绪状态，为抢占式调度。该进程处于等待状态，且优先级较高，当等待的事件发生了，该进程会转为就绪态，而调度算法是根据优先级进行调度的，于是会抢占正在运行的进程，就会发生CPU调度。
						</p>
						<p>非抢占式调度：进程运行时，会一直运行，直到进程完成或者发送某个事件被阻塞时，才会把CPU让给其他进程。</p>
						<p>抢占式调度：正在运行的进程可以被打断，使其把CPU让给其他进程。抢占原则分三种：时间片原则、优先权原则、短作业优先原则。</p>
					</li>
				</ul>
				<h4 id="-">进程调度的基本原则</h4>
				<ul>
					<li><strong>CPU 利用率</strong>：调度程序应确保 CPU 是始终匆忙的状态，这可提高 CPU 的利用率；</li>
					<li><strong>系统吞吐量</strong>：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量；
					</li>
					<li><strong>周转时间</strong>：周转时间是进程运行+阻塞时间+等待时间的总和，一个进程的周转时间越小越好；</li>
					<li><strong>等待时间</strong>：这个等待时间不是阻塞状态的时间，而是进程处于就绪队列的时间，等待的时间越长，用户越不满意；</li>
					<li><strong>响应时间</strong>：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。</li>
				</ul>
				<h4 id="-">进程调度算法</h4>
				<table>
					<thead>
						<tr>
							<th>算法(是否抢占式)</th>
							<th>运行规则</th>
							<th>优缺点(饥饿)</th>
						</tr>
					</thead>
					<tbody>
						<tr>
							<td>先来先服务调度算法FCFS(否)</td>
							<td>按照请求的顺序进行调度</td>
							<td>有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。（不会）</td>
						</tr>
						<tr>
							<td>最短作业优先调度算法SJF(都有)</td>
							<td>按估计运行时间最短的顺序进行调度。</td>
							<td>长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。（会）</td>
						</tr>
						<tr>
							<td>高响应比优先调度算法HRRN(否)</td>
							<td>每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行。<br />优先权 = （等待时间+要求服务时间）/ 要求服务时间。</td>
							<td>每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行。<strong>但是这是比较理想的情况，因为我们无法确定服务时间</strong>。(不会)
							</td>
						</tr>
						<tr>
							<td>时间片轮转调度算法RR</td>
							<td>每个进程被分配一个时间段，称为时间片，即允许该进程在该时间段中运行。如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配给另外一个进程。
							</td>
							<td>1.如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率； <br />2.如果设得太长又可能引起对短作业进程的响应时间变长。(不会)</td>
						</tr>
						<tr>
							<td>最高优先调度算法HPF(都有)</td>
							<td>根据任务的紧急程度来决定处理顺序</td>
							<td>若源源不断的高优先级进程到来，低优先级进程会导致饥饿。(会)</td>
						</tr>
						<tr>
							<td>多级反馈队列调度算法MFQ(是)</td>
							<td>「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
								<br />「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；</td>
							<td>对各类进程相对公平（FCFS）；每个新到来的进程都可以很快得到相应(RR)；短进程只用较少的时间就可以完成(SPF)；不必实现估计进程的时间；灵活地调整对各种进程的偏好程度
							</td>
						</tr>
					</tbody>
				</table>
				<h3 id="-">进程通信方式</h3>
				<ul>
					<li>
						<p><strong>管道</strong>，管道数据传输是单向的。进程读写的数据都是缓存在<strong>内核</strong>中。不适合频繁交换数据。</p>
						<ul>
							<li>匿名管道，只能在具有亲缘关系的进程之间使用。</li>
						</ul>
						<p>优点：简单方便</p>
						<p>缺点：局限于单向通信；只能创建在它的进程以及其有亲缘关系的进程之间；缓冲区有限；</p>
						<ul>
							<li>有名管道，允许在没有亲缘关系的进程之间使用。</li>
						</ul>
						<p>优点：可以实现任意关系的进程间的通信</p>
						<p>缺点：长期存于系统中，使用不当容易出错；缓冲区有限</p>
					</li>
					<li>
						<p><strong>消息队列</strong>，消息队列是<strong>有消息的链表</strong>，<strong>存放在内核中</strong>并由消息队列标识符标识。</p>
					</li>
				</ul>
				<p>优点，消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点，可以频繁交换数据。</p>
				<p>缺点，消息队列不适合比较大数据的传输，在通信过程中存在用户态与内核态之间的数据拷贝开销(写入数据时需要把数据从用户态拷贝到内核态，读取数据时又要把数据从内核态拷贝回用户态)。</p>
				<ul>
					<li><strong>共享内存</strong>，共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与信号量，配合使用来实现进程间的同步和通信。
					</li>
				</ul>
				<p>优点，无须复制，快捷，信息量大。</p>
				<p>缺点，需要考虑多进程竞争共享临界资源。</p>
				<ul>
					<li><strong>信号量</strong>，可以<strong>保护共享的资源，在任意时刻只能被一个进程访问</strong>，<strong>主要用于实现进程间或者同一进程内不同线程之间的的互斥与同步</strong>，也常作一种锁机制。
					</li>
				</ul>
				<p>运行机制，信号量初始化为1，表示互斥信号量，为0表示同步信号量。P操作信号量-1就是wait，V操作信号量+1就是post。</p>
				<p>优点，可以同步进程</p>
				<p>缺点，信号量有限。</p>
				<ul>
					<li><strong>信号</strong>，<strong>对于异常情况下的工作模式，就需要用「信号」的方式来通知进程。</strong>是进程间通信机制中<strong>唯一的异步通信机制</strong>
					</li>
				</ul>
				<p><strong>1.执行默认操作</strong>。Linux 对每种信号都规定了默认操作。</p>
				<p><strong>2.捕捉信号</strong>。我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。</p>
				<p><strong>3.忽略信号</strong>。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 <code>SIGKILL</code> 和
					<code>SEGSTOP</code>，它们用于在任何时候中断或结束某一进程。</p>
				<ul>
					<li>socket，<strong>跨网络与不同主机上的进程之间通信。</strong></li>
				</ul>
				<p><strong>本地socket</strong>被用于在<strong>同一台主机上进程间通信</strong>的场景：
					在bind的时候，不像TCP和UDP要绑定IP地址和端口，而是<strong>绑定一个本地文件</strong>，这也就是它们之间的最大区别。</p>
				<h2 id="-">线程</h2>
				<p>线程是进程当中的一条执行流程，是调度的基本单位。</p>
				<p>同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。</p>
				<h3 id="-">线程优缺点</h3>
				<p>线程的优点：</p>
				<ul>
					<li>一个进程中可以同时存在多个线程；</li>
					<li>各个线程之间可以并发执行；</li>
					<li>各个线程之间可以共享地址空间和文件等资源；</li>
				</ul>
				<p>线程的缺点：</p>
				<ul>
					<li>当进程中的一个线程崩溃时，会导致其所属进程的所有线程崩溃</li>
				</ul>
				<h3 id="-">线程相比进程能减少开销</h3>
				<ul>
					<li>线程的<strong>创建时间比进程快</strong>，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；
					</li>
					<li>线程的终止时间比进程快，因为线程<strong>释放的资源相比进程少</strong>很多；</li>
					<li>同一个进程内的线程切换比进程<strong>切换快</strong>，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；
					</li>
					<li>由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的<strong>数据交互效率更高</strong>；</li>
				</ul>
				<h3 id="-">线程实现</h3>
				<ul>
					<li><strong>用户线程</strong>：在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库来完成线程的管理；</li>
					<li><strong>内核线程</strong>：在内核中实现的线程，是由内核管理的线程；</li>
					<li><strong>轻量级进程</strong>：在内核中来支持用户线程；</li>
				</ul>
				<h2 id="-">锁</h2>
				<p>多线程访问共享资源的时候，避免不了资源竞争而导致数据错乱的问题，所以我们通常为了解决这个问题，都会在访问共享资源之前加锁。</p>
				<h3 id="-">悲观锁</h3>
				<p>悲观锁做事比较悲观，它认为<strong>多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁</strong>。</p>
				<h4 id="-">互斥锁</h4>
				<p>互斥锁是一种独占锁，当前线程加锁成功时，其他线程会<strong>加锁失败被阻塞</strong>，在多线程条件下可以防止共享资源被并发访问，造成数据错乱。</p>
				<p>互斥锁是在抢锁失败的情况下主动放弃CPU进入睡眠状态直到锁的状态改变时再唤醒，而操作系统负责线程调度，为了实现锁的状态发生改变时唤醒阻塞的线程或者进程，需要把锁交给操作系统管理，所以互斥锁在加锁操作时涉及上下文的切换。<strong>存在一种情况，就是可能两次上下文切换的时间要锁住代码的时间比你锁住的代码执行时间要长，这个时候应该选择自旋锁，或者以下解决方案。</strong>
				</p>
				<p>互斥锁的一种可能的实现是先自旋一段时间，当自旋的时间超过阀值之后再将线程投入睡眠中，因此在并发运算中使用互斥锁（每次占用锁的时间很短）的效果可能不亚于使用自旋锁。</p>
				<h4 id="-">自旋锁</h4>
				<p>如果进线程无法取得锁，进线程不会立刻放弃CPU时间片，而是一直循环尝试获取锁，直到获取为止。如果别的线程长时期占有锁，那么自旋就是在浪费CPU做无用功，但是自旋锁一般应用于加锁时间很短的场景，这个时候效率比较高。
				</p>
				<p>相比于互斥锁虽然使用层面比较相似，但是实现层面上完全不同：<strong>当加锁失败时，互斥锁用「线程切换」来应对，自旋锁则用「忙等待」来应对</strong>。</p>
				<h4 id="-">条件变量</h4>
				<p>互斥锁一个明显的缺点是他只有两种状态：锁定和非锁定。而条件变量通过允许线程阻塞和等待另一个线程发送信号的方法弥补了互斥锁的不足，他常和互斥锁一起使用，以免出现竞态条件。当条件不满足时，线程往往解开相应的互斥锁并阻塞线程然后等待条件发生变化。一旦其他的某个线程改变了条件变量，他将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。总的来说<strong>互斥锁是线程间互斥的机制，条件变量则是同步机制</strong>。
				</p>
				<pre><code class="lang-c++">pthread_cond_wait(&amp;cond, &amp;mutex);//当这个函数调用阻塞的时候，会对互斥锁进行解锁，当不阻塞的，继续向下执行，会重新加锁。
</code></pre>
				<h4 id="-">读写锁</h4>
				<p>读写锁可以用互斥锁和自旋锁实现。</p>
				<p>读写锁是一把锁，它有读和写两个状态，当“写锁”没有被线程持有的时候，多个线程可以共同持有”读锁“，读取共享资源。一旦“写锁”被线程持有，那些想要获取“读锁”的线程和想要获取“写锁”的线程都会被阻塞，任意时刻只允许一个线程持有写锁，在读多写少的时候应该选择读写锁。
				</p>
				<h3 id="-">乐观锁</h3>
				<p>只有在冲突概率非常低，且加锁成本非常高的场景时，才考虑使用乐观锁。</p>
				<p>乐观锁做事比较乐观，它假定冲突的概率很低，它的工作方式是：<strong>先修改完共享资源，再验证这段时间内有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作</strong>。
				</p>
				<h3 id="-">死锁</h3>
				<p><strong>多个进程在执行过程中，因为争夺资源出现了进程相互之间无限期阻塞等待的状态就是死锁。</strong></p>
				<h4 id="-">死锁产生条件</h4>
				<ol>
					<li><strong>互斥条件</strong>：进程对所需求的资源具有排他性，若有其他进程请求该资源，请求进程只能等待。</li>
					<li><strong>不剥夺条件</strong>：进程在所获得的资源未释放前，不能被其他进程强行夺走，只能自己释放。</li>
					<li><strong>请求和保持条件</strong>：进程当前所拥有的资源在进程请求其他新资源时，由该进程继续占有。</li>
					<li><strong>循环等待条件</strong>：存在一种进程资源循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。</li>
				</ol>
				<h4 id="-">死锁避免方案</h4>
				<ul>
					<li>保证上锁顺序一致</li>
					<li>使用资源有序分配，来破坏环路</li>
				</ul>
				<h4 id="-">处理方法</h4>
				<ul>
					<li>
						<p>鸵鸟策略，就不是不管它，因为解决死锁问题代价很高。</p>
					</li>
					<li>
						<p>死锁检测，不试图阻止死锁，而是检测到死锁发生时，采取措施进行恢复。</p>
					</li>
					<li>死锁恢复，<ul>
							<li>利用抢占恢复</li>
							<li>利用回滚恢复</li>
							<li>通过杀死进程恢复</li>
						</ul>
					</li>
					<li>死锁预防，<ul>
							<li>破坏互斥条件，例如假脱机打印机技术允许若干个进程同时输出。</li>
							<li>破坏请求的保持条件，可以规定所以进程在开始执行前请求所需要的全部资源</li>
							<li>破坏不剥夺条件，允许抢占资源</li>
							<li>破坏循环请求等待，给资源统一编号，进程只能按编号顺序来请求资源</li>
						</ul>
					</li>
					<li>死锁避免，在程序运行时避免死锁<ul>
							<li>安全状态</li>
							<li>单个资源的银行家算法</li>
							<li>多个资源的银行家算法</li>
							<li>检查一个状态是否安全的算法</li>
						</ul>
					</li>
				</ul>
				<h2 id="-">进程同步问题</h2>
				<h3 id="-">生产者与消费者问题</h3>
				<p><img src="https://cdn.xiaolincoding.com/gh/xiaolincoder/ImageHost/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/%E4%BA%92%E6%96%A5%E4%B8%8E%E5%90%8C%E6%AD%A5/20-%E7%94%9F%E4%BA%A7%E8%80%85%E6%B6%88%E8%B4%B9%E8%80%85.jpg"
						alt=""></p>
				<p>问题描述：</p>
				<ul>
					<li><strong>生产者</strong>在生成数据后，放在一个缓冲区中；</li>
					<li><strong>消费者</strong>从缓冲区取出数据处理；</li>
					<li>任何时刻，<strong>只能有一个</strong>生产者或消费者可以访问缓冲区；</li>
				</ul>
				<p>分析：</p>
				<ul>
					<li>任何时刻只能有一个线程操作缓冲区，说明操作缓冲区是临界代码，<strong>需要互斥</strong>；</li>
					<li>缓冲区空时，消费者必须等待生产者生成数据；缓冲区满时，生产者必须等待消费者取出数据。说明生产者和消费者<strong>需要同步</strong></li>
				</ul>
				<p>需要三个信号量：</p>
				<ul>
					<li>互斥信号量 <code>mutex</code>：用于互斥访问缓冲区，初始化值为 1；</li>
					<li>资源信号量 <code>fullBuffers</code>：用于消费者询问缓冲区是否有数据，有数据则读取数据，初始化值为 0（表明缓冲区一开始为空）；</li>
					<li>资源信号量 <code>emptyBuffers</code>：用于生产者询问缓冲区是否有空位，有空位则生成数据，初始化值为 n （缓冲区大小）；</li>
				</ul>
				<h3 id="-">哲学家进餐问题</h3>
				<p><img src="https://cdn.xiaolincoding.com/gh/xiaolincoder/ImageHost/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/%E4%BA%92%E6%96%A5%E4%B8%8E%E5%90%8C%E6%AD%A5/23-%E5%93%B2%E5%AD%A6%E5%AE%B6%E8%BF%9B%E9%A4%90%E6%A8%A1%E5%9E%8B.jpg"
						style="zoom:50%;" /></p>
				<p>问题描述：</p>
				<p>五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。</p>
				<p>错误操作：如果所以哲学家拿起左边筷子，会导致死锁。</p>
				<p>解决方案（1.必须同时拿起左右两根筷子，只有两个邻居都没有进餐的情况下才允许进餐）</p>
				<ul>
					<li>方案一，只要有一个哲学家进入临界区，也就是准备拿叉子时，其他哲学家都不能动，只有这位哲学家用完叉子，才能轮到下一位。(效率低)</li>
					<li>方案二，让偶数编号的哲学家先拿左边的叉子后拿右边的叉子，奇数编号的哲学家先拿右边的叉子后拿左边的叉子。</li>
					<li>方案三，用一个数组 state 来记录每一位哲学家的三个状态，分别是在进餐状态、思考状态、饥饿状态（正在试图拿叉子）</li>
				</ul>
				<h3 id="-">读者写者问题</h3>
				<p>问题描述：</p>
				<ul>
					<li>「读-读」允许：同一时刻，允许多个读者同时读</li>
					<li>「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写</li>
					<li>「写-写」互斥：没有其他写者时，写者才能写</li>
				</ul>
				<p>解决方案：</p>
				<ul>
					<li>方案一，读者有优先，只要有读者正在读的状态，后来的读者都可以进入，但写者可能会处于饥饿状态。</li>
					<li>方案二，写者优先策略。<ul>
							<li>只要有写者准备写入，写者应尽快执行写操作，后来读者必须阻塞。</li>
							<li>如果有写者持续不断写入，则读者就处于饥饿。</li>
						</ul>
					</li>
					<li>方案三，公平策略<ul>
							<li>优先级相同；</li>
							<li>写者、读者互斥访问；</li>
							<li>只能一个写者访问临界区；</li>
							<li>可以有多个读者同时访问临界资源；</li>
						</ul>
					</li>
				</ul>
				<h2 id="-">其他问题</h2>
				<h3 id="-">进程与线程</h3>
				<table>
					<thead>
						<tr>
							<th></th>
							<th>进程</th>
							<th>线程</th>
							<th>协程</th>
						</tr>
					</thead>
					<tbody>
						<tr>
							<td>定义</td>
							<td>资源分配和拥有的基本单位</td>
							<td>程序执行的基本单位</td>
							<td>用户态的轻量级线程，线程内部调度的基本单位</td>
						</tr>
						<tr>
							<td>切换情况</td>
							<td>进程CPU环境的保存以及新调度进程CPU环境设置(栈、寄存器、页表和文件句柄)</td>
							<td>保存和设置程序计数器、少量寄存器和栈的内容</td>
							<td>用户</td>
						</tr>
						<tr>
							<td>切换者</td>
							<td>操作系统</td>
							<td>操作系统</td>
							<td></td>
						</tr>
						<tr>
							<td>切换过程</td>
							<td>用户态、内核态、用户态</td>
							<td>用户态，内核态，用户态</td>
							<td>用户态(没有陷入内核)</td>
						</tr>
						<tr>
							<td>调用栈</td>
							<td>内核栈</td>
							<td>内核栈</td>
							<td>用户栈</td>
						</tr>
						<tr>
							<td>拥有资源</td>
							<td>CPU资源、内存资源、文件资源、句柄</td>
							<td>程序计数器、寄存器、栈和状态字</td>
							<td>用于自己的寄存器上下文和栈</td>
						</tr>
						<tr>
							<td>并发性</td>
							<td>不同进程之间切换实现并发，各自占有CPU实现并行</td>
							<td>一个进程内部的多个线程并发执行</td>
							<td>同一时间只能执行一个协程，而其他协程处于休眠状态，适合对任务进行分时处理</td>
						</tr>
						<tr>
							<td>系统开销</td>
							<td>切换虚拟地址空间，切换内核栈和硬件上下文，CPU告诉缓存失效、页表切换、开销很大</td>
							<td>切换时只需保存和设置少量寄存器内容，因此开销很少</td>
							<td>直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文切换非常快</td>
						</tr>
						<tr>
							<td>通信方面</td>
							<td>进程间通信需要操作系统</td>
							<td>线程间可以之间读写进程数据段(如全局变量)来进行通信</td>
							<td>共享内存、消息队列</td>
						</tr>
					</tbody>
				</table>
				<p><strong>线程与进程的比较</strong></p>
				<p>1、线程启动速度快，轻量级</p>
				<p>2、线程的系统开销小</p>
				<p>3、线程使用有一定难度，需要处理数据一致性问题</p>
				<p>4、同一线程共享的有堆、全局变量、静态变量、指针，引用、文件等，而独自占有栈</p>
				<h3 id="-">一个进程最多可以创建多少个线程</h3>
				<p>相关，</p>
				<ul>
					<li><strong>进程的虚拟内存空间上限</strong>，因为创建一个线程，操作系统需要为其分配一个栈空间，如线程数量越多，所需栈空间就要越大，那么虚拟内存就会占用的越多。</li>
					<li><strong>系统参数限制</strong>，虽然Linux并没有内核参数来控制单个进程创建的最大线程个数，但是又系统级别的参数来控制整个系统的最大线程个数。</li>
				</ul>
				<p>总结，</p>
				<ul>
					<li>32位系统，用户态的虚拟空间只有3G，如果创建线程时分配的栈空间是10M，那么一共进程最多只能创建300个左右的线程</li>
					<li>64位系统用户态的虚拟空间128T，理论上不会受虚拟内存大小的限制，而会受系统参数或性能限制。</li>
				</ul>
				<h3 id="-">线程崩溃了，进程也会崩溃吗</h3>
				<ul>
					<li>原因</li>
				</ul>
				<p><strong>如果线程是因为非法访问内存引起的崩溃，那么进程肯定会崩溃</strong>。因为进程中各个线程的地址空间是共享，那么某个线程对地址的非法访问就会导致<strong>内存的不确定性</strong>，进而可能会影响到其他线程，所以这种操作是危险的，则操作系统干脆让整个进程崩溃。
				</p>
				<ul>
					<li>
						<p>如何崩溃</p>
					</li>
					<li>
						<p>CPU 执行正常的进程指令</p>
					</li>
					<li>调用 kill 系统调用向进程发送信号</li>
					<li>进程收到操作系统发的信号，CPU 暂停当前程序运行，并将控制权转交给操作系统</li>
					<li>调用 kill 系统调用向进程发送信号（假设为 11，即 SIGSEGV，一般非法访问内存报的都是这个错误）</li>
					<li><strong>操作系统根据情况执行相应的信号处理程序（函数），一般执行完信号处理程序逻辑后会让进程退出</strong></li>
				</ul>
				<h3 id="-">会话、作业、进程组、父进程、子进程</h3>
				<h1 id="-">内存管理</h1>
				<p>内存管理，操作系统的工作：</p>
				<ul>
					<li>负责内存空间的分配和回收</li>
					<li>提供某种技术从逻辑上对内存空间进行扩充</li>
					<li>提供地址转换功能，负责程序的逻辑地址与物理地址的转换</li>
					<li>提供内存保护功能，保证各进程在各自存储空间内运行互不干扰。</li>
				</ul>
				<h2 id="-">虚拟内存</h2>
				<p>操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来。</p>
				<ul>
					<li>我们程序所使用的内存地址叫做<strong>虚拟内存地址</strong>。</li>
					<li>实际存在硬件里面的空间地址叫<strong>物理内存地址</strong>。</li>
				</ul>
				<p>进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存</p>
				<p>操作系统管理虚拟地址与物理地址之间的关系，主要通过两个方式，<strong>内存分段和内存分页</strong>。</p>
				<h3 id="-"><strong>虚拟内存的作用</strong></h3>
				<ul>
					<li>第一，虚拟内存可以<strong>使得进程对运行内存超过物理内存大小</strong>，因为程序运行符合局部性原理，CPU
						访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，我们可以把它换出到物理内存之外，比如硬盘上的 swap 区域。</li>
					<li>第二，由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了<strong>多进程之间地址冲突</strong>的问题。
					</li>
					<li>第三，页表里的页表项中除了物理地址之外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在等。在内存访问方面，操作系统提供了<strong>更好的安全性</strong>。
					</li>
				</ul>
				<h3 id="-">内存分段</h3>
				<p>程序是由若干个逻辑分组组成的，可由<strong>代码分段，数据分段，栈段，堆段</strong>组成。不同的段是有不同的属性的，所以就用分段的形式把这些段分离。</p>
				<p>分段机制下，虚拟地址由两部分组成，<strong>段选择因子和段内偏移量</strong>。</p>
				<ul>
					<li><strong>段选择因子</strong>就保存在段寄存器里面。段选择因子里面最重要的是<strong>段号</strong>，用作段表的索引。<strong>段表</strong>里面保存的是这个<strong>段的基地址、段的界限和特权等级</strong>等。
					</li>
					<li>虚拟地址中的<strong>段内偏移量</strong>应该位于 0 和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址。、</li>
				</ul>
				<h4 id="-">内存分段优缺点</h4>
				<p>优点</p>
				<ul>
					<li>解决了程序本身不需要关心具体物理内存地址的问题</li>
				</ul>
				<p>缺点</p>
				<ul>
					<li>外部内存碎片</li>
				</ul>
				<p>内存分段管理可以做到段根据实际需求分配内存，所以有多少需求就分配多大的段，<strong>不会出现内部内存碎片</strong>，但是由于每个段的长度不固定，所以<strong>多个段未必能恰好使用所有的内存空间</strong>，会产生多个不连续的小物理内存，导致新的程序无法被装载，<strong>容易出现外部内存碎片</strong>。
				</p>
				<p>解决方法，<strong>内存交换</strong>，将运行内存写到硬盘上，再从硬盘上读回来，但此时装载的位置是紧跟着被使用的内存。<strong>在Linux系统里，就是Swap空间，专门用于内存与硬盘的空间交换</strong>。
				</p>
				<ul>
					<li>内存交换效率低</li>
				</ul>
				<p>硬盘访问速度比内存慢太多，每一次内存交换，都需要把一大段内存数据写到硬盘上，如果内存交换的是一个占内存空间很大的程序，这样整个机器就会显得卡顿。</p>
				<h3 id="-">内存分页</h3>
				<p><strong>分页是把整个虚拟和物理内存切成一段段固定尺寸大小</strong>，这样一个连续并且尺寸固定的内存空间，我们叫页。</p>
				<p>页表存储在内存里，<strong>内存管理单元</strong>（MMU）将虚拟内存地址转换成物理地址。</p>
				<p>当进程访问虚拟地址在页表中查不到时，系统就会产生一个<strong>缺页异常</strong>，进入系统内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程运行。</p>
				<h4 id="-">分页映射机制</h4>
				<p>在分页机制下，虚拟地址分为两部分，<strong>页号</strong>和<strong>页内偏移</strong>。页号作为页表的索引，<strong>页表</strong>包含物理页每页所在<strong>物理内存的基地址</strong>，这个基地址与页内偏移的组合就形成了物理内存地址
				</p>
				<p><img src="https://cdn.xiaolincoding.com//mysql/other/7884f4d8db4949f7a5bb4bbd0f452609.png"
						style="zoom: 67%;" /></p>
				<p>三个步骤：</p>
				<ul>
					<li>把虚拟内存地址，切分成页号和偏移量</li>
					<li>根据页号，从页表里面，查询对应的物理页号</li>
					<li>直接那物理页号，加上前面的偏移量，得到物理内存地址。</li>
				</ul>
				<h4 id="-">内存分页优缺点</h4>
				<p>优点（解决外部内存碎片和内存交换效率低的问题）</p>
				<ul>
					<li><strong>能产生连续的内存空间</strong>，内存分页由于内存空间预先划分好，页与页之间是紧密排列的，所以不会产生外部碎片。</li>
					<li><strong>相对于内存分段，内存分页的交换效率更高。</strong>如果内存空间不够，操作系统会把其他正在运行的进程中的最近没被使用的内存页面释放掉。所以一次性写入磁盘的也只有少数的一个页或者几个页，此时内存交换效率相对比较快。同时我们完全可以在进行虚拟内存和物理内存的页之间的映射之后，并不真的需要把页加载到物理内存里，而<strong>只有在程序运行中，需要用到对应虚拟内存页里面的指令和数据时，在加载到物理内存里。</strong>
					</li>
				</ul>
				<p>缺点</p>
				<ul>
					<li><strong>会出现内部内存碎片</strong>。因为分页机制分配内存最小单位是一页，即使程序不足一页大小，也会分配一页，所以内存分页机制会出现内部碎片。</li>
					<li><strong>页表可能会很庞大</strong>。一个进程的页表需要装下100多万个页表项，并且每个页表项占4字节，每个页表占4MB。</li>
				</ul>
				<h4 id="-">多级页表</h4>
				<ul>
					<li>为什么多级页表所占空间更少。</li>
				</ul>
				<p><strong>如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表</strong>。</p>
				<p>对于64位系统，有四级目录，</p>
				<ul>
					<li>全局页目录项 PGD（<em>Page Global Directory</em>）；</li>
					<li>上层页目录项 PUD（<em>Page Upper Directory</em>）；</li>
					<li>中间页目录项 PMD（<em>Page Middle Directory</em>）；</li>
					<li>页表项 PTE（<em>Page Table Entry</em>）；</li>
				</ul>
				<p><strong>TLB(快表)</strong></p>
				<p>多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，也就是带来了时间上的开销。程序时由局部性的，即在一段时间内，整个程序的执行仅限于程序的某一个部分，相应的，执行访问储存空间也局限某个内存区域。
				</p>
				<p>TLB，就是在CPU中，专门存放程序最常访问的页表项的Cache，一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。</p>
				<h4 id="-">地址变换过程</h4>
				<table>
					<thead>
						<tr>
							<th>是否有快表</th>
							<th>地址变换过程</th>
							<th>访问一个逻辑地址访存次数</th>
						</tr>
					</thead>
					<tbody>
						<tr>
							<td>无</td>
							<td>1.算页号、页内偏移量 2.检查页号合法性 3.查页表，找到页面存放的内存块号 4.根据内存块号与页内偏移量得到物理地址 5.访问目标内存单元</td>
							<td>两次访存</td>
						</tr>
						<tr>
							<td>有</td>
							<td>1.算页号、页内偏移量 2.检查页号合法性 <strong>3.查快表。若命中，即可知道页面存放的内存块号，可直接进行(5)；若未命中，进行(4)</strong>
								4.查页表，找到页面存放的内存块号，并将页表项复制到快表中 5.根据内存块号与页内偏移量得到物理地址 6.访问目标内存单元</td>
							<td>快表命中，一次<br />快表未命中，两次</td>
						</tr>
					</tbody>
				</table>
				<p>两次访存解释：</p>
				<ul>
					<li>第一次从内存中找到页表，然后找到页面的物理块号，加上页内偏移得到实际物理地址</li>
					<li>第二次根据第一次得到的物理地址访问内存取出数据</li>
				</ul>
				<p>一次存解释：</p>
				<p>命中快表，直接从快表中读取响应物理块号。</p>
				<p><img src="http://oss.interviewguide.cn/img/202205212343703.png" style="zoom: 67%;" /></p>
				<h4 id="-">分页算法</h4>
				<table>
					<thead>
						<tr>
							<th>算法</th>
							<th>算法规则</th>
							<th>优点</th>
						</tr>
					</thead>
					<tbody>
						<tr>
							<td>最佳置换算法OPT</td>
							<td>优先淘汰最长时间内不会被访问的页面</td>
							<td>缺页率最小，性能最好，但无法实现</td>
						</tr>
						<tr>
							<td>先进先出置换算法FIFO</td>
							<td>优先淘汰最先进入内存的页面</td>
							<td>实现简单，但性能差，可能出现Belady异常</td>
						</tr>
						<tr>
							<td>最近最久未使用置换算法LRU</td>
							<td>优先淘汰最近最久没访问的页面</td>
							<td>性能很好，但需要硬件支持，算法开销大</td>
						</tr>
						<tr>
							<td>时钟置换算法CLOCK（NRU）</td>
							<td>循环扫描个页面 第一轮淘汰访问位=0的， 并将扫描过得页面访问位改为1.若第1轮没选中，则进行第二轮扫描</td>
							<td>实现简单，算法开销小，单位考虑页面是否被修改过</td>
						</tr>
						<tr>
							<td>改进型时钟置换算法</td>
							<td>若用（访问位，修改位）形式表述，则第一轮淘汰（0,0）第二轮淘汰（0,1），并将扫描过的页面访问位都置为0 第三轮淘汰（0,0）第四轮淘汰（0,1）</td>
							<td>顺丰开销较小，性能不错</td>
						</tr>
					</tbody>
				</table>
				<h3 id="-">段页式内存管理</h3>
				<p>地址结构就由<strong>段号、段内页号和页内位移</strong>三部分组成。</p>
				<p>管理实现方式：</p>
				<ul>
					<li>将程序划分为多个有逻辑意义的段，也就是分段机制</li>
					<li>接着吧每个段划分为多个页，也就是对分段划分出来的连续空间，再划分固定大小的页</li>
				</ul>
				<p>用于段页式地址变换的数据结构是每一个程序一张段表，每个段又建立一张页表，段表中的地址是页表的起始地址，而页表中的地址则为某页的物理页号</p>
				<p>段页式的<strong>三次访存</strong>：</p>
				<ul>
					<li>第一次，访问段表，得到页表起始地址</li>
					<li>第二次，访问页表，得到物理页号</li>
					<li>第三次，将物理页号与页内位移组合，得到物理地址</li>
				</ul>
				<p>特点：可<strong>用软、硬件相结合的方法实现段页式地址变换，这样虽然增加了硬件成本和系统开销，但提高了内存的利用率。</strong></p>
				<h3 id="-">动态分区算法</h3>
				<table>
					<thead>
						<tr>
							<th>算法</th>
							<th>算法思想</th>
							<th>分区排列顺序</th>
							<th>优点</th>
							<th>缺点</th>
						</tr>
					</thead>
					<tbody>
						<tr>
							<td>首次适应</td>
							<td>从头到尾找到适合分区</td>
							<td>空闲分区以地址递增次序排列</td>
							<td>综合性能最好。算法开销小，回收分区一般不需要对空闲分区队列重新排序</td>
							<td></td>
						</tr>
						<tr>
							<td>最佳适应</td>
							<td>优先使用更小的分区，以保留更多大分区</td>
							<td>空闲分区以容量递增次序排序</td>
							<td>会有更多的大分区被保留下来，更能满足大进程需求</td>
							<td>会产生很多太小的，难以利用的碎片；算法开销大，回收分区后可能需要对空闲分区队列重新排序</td>
						</tr>
						<tr>
							<td>最坏适应</td>
							<td>优先使用更大分区，以防止产生太小的不可用的碎片</td>
							<td>空闲分区以容量递减次序排序</td>
							<td>可以减少难利用的小碎片</td>
							<td>大分区容易被用完，不利于大进程；算法开销大；算法开销大</td>
						</tr>
						<tr>
							<td>邻近适应</td>
							<td>由首次适应演变而来，每次从上次查找结束位置开始查找</td>
							<td>空闲分区以地址递增次序排序（可排序成循环链表）</td>
							<td>不用每次都从低地址的小分区开始检索。算法开销小（原因同首次适应算法）</td>
							<td>会使高地址的大分区也被用完</td>
						</tr>
					</tbody>
				</table>
				<h2 id="-">内存分配</h2>
				<h3 id="-">内存布局</h3>
				<p><img src="https://cdn.xiaolincoding.com/gh/xiaolincoder/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/%E8%99%9A%E6%8B%9F%E5%86%85%E5%AD%98/32%E4%BD%8D%E8%99%9A%E6%8B%9F%E5%86%85%E5%AD%98%E5%B8%83%E5%B1%80.png"
						style="zoom:50%;" /></p>
				<p>用户态分布：</p>
				<ul>
					<li>栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是 <code>8 MB</code>。当然系统也提供了参数，以便我们自定义大小；<strong>从高到低增长</strong>
					</li>
					<li>文件映射段，包括动态库、共享内存等，<strong>从低地址开始向上增长</strong>(跟硬件和内核版本有关)；</li>
					<li>堆段，包括动态分配的内存，<strong>从低地址开始向上增长</strong>；</li>
					<li>BSS 段，包括未初始化的静态变量和全局变量；</li>
					<li>数据段，包括已初始化的静态常量和全局变量；</li>
					<li>代码段，包括二进制可执行代码；</li>
					<li>灰色区域，保留区，在大多数系统里我们认为较小数值的地址不是一个合法地址。是防止程序出现bug，导致读写一些小内存地址数据，使得程序跑飞。</li>
				</ul>
				<p><strong>注</strong>：堆和文件映射区是动态分配的，C标准库的malloc()与mmap()，就可以分别在堆和文件映射动态分配内存。</p>
				<h3 id="malloc-">malloc（申请虚拟内存）</h3>
				<p><strong>malloc 申请内存的时候，会有两种方式向操作系统申请堆内存。</strong>malloc函数不是系统调用，是c库函数，用于动态分配，同时malloc分配的是虚拟内存。</p>
				<ul>
					<li>方式一：通过 brk() 系统调用从堆分配内存（用户分配的内存小于 128 KB）</li>
					<li>方式二：通过 mmap() 系统调用在文件映射区域分配内存（用户分配的内存大于 128 KB）；</li>
				</ul>
				<p><strong>free释放内存，会归还操作系统吗</strong></p>
				<ul>
					<li>brk()，并不会，被free挥手的内存会首先被ptmalloc使用双链表保存起来，当用户下一次申请内存时，会尝试从这些内存中寻找合适的返回。同时ptmalloc也会尝试对小块内存进行合并。（避免了频繁的系统调用，占用过多的系统资源，避免过多的内存碎片。）
					</li>
					<li>mmap()，归还操作系统，直接释放</li>
				</ul>
				<p><strong>为什么malloc返回的内存试试地址比进程堆空间起始地址多16字节</strong></p>
				<p>多出来16字节是保存该内存块描述信息，比如内存块大小。</p>
				<p>当执行free函数，free会对传入进来的内存地址向左便宜16字节，从16字节分析出内存块大小，自然中的要释放多大内存。</p>
				<h4 id="mmap-">mmap缺点</h4>
				<ul>
					<li>mmap向操作系统申请内存需要通过系统调用，如果都用mmap来分配内存，等于每次都要执行系统调用</li>
					<li>mmap分配内存每次释放都要归还操作系统，于是每次mmap分配的虚拟地址都是缺页状态，在第一次访问该虚拟地址的时候，都会触发缺页中断。消耗CPU过大。</li>
				</ul>
				<p>注：缺页表示，读到的虚拟地址，未被加载到内存，需要磁盘读入。</p>
				<h4 id="brk-">brk缺点</h4>
				<ul>
					<li>优势(相比于mmap)：</li>
				</ul>
				<p>malloc 通过 brk() 系统调用在堆空间申请内存的时候，由于堆空间是连续的，所以直接预分配更大的内存来作为内存池，当内存释放的时候，就缓存在内存池中。</p>
				<p><strong>等下次在申请内存的时候，就直接从内存池取出对应的内存块就行了，而且可能这个内存块的虚拟地址与物理地址的映射关系还存在，这样不仅减少了系统调用的次数，也减少了缺页中断的次数，这将大大降低
						CPU 的消耗</strong>。</p>
				<ul>
					<li>缺点：</li>
				</ul>
				<p>系统频繁使用malloc与free，堆内回产生越来越多的不可用的碎片，导致“内存泄漏”，这种泄漏现象是valgrind无法检测的。</p>
				<h4 id="-">缺页中断</h4>
				<p>应用程序通过 malloc 函数申请内存的时候，实际上申请的是虚拟内存，此时并不会分配物理内存。</p>
				<p>当应用程序读写了这块虚拟内存，CPU 就会去访问这个虚拟内存， 这时会发现这个虚拟内存没有映射到物理内存， CPU
					就会产生<strong>缺页中断</strong>，进程会从用户态切换到内核态，并将缺页中断交给内核的 Page Fault Handler （缺页中断函数）处理。</p>
				<p>缺页中断处理函数会看是否有空闲的物理内存：</p>
				<ul>
					<li>如果有，就直接分配物理内存，并<strong>建立虚拟内存与物理内存之间的映射关系</strong>。</li>
					<li>如果没有空闲的物理内存，那么内核就会开始进行回收内存的工作，如果回收内存工作结束后，空闲的物理内存仍然无法满足此次物理内存的申请，那么内核就会放最后的大招了触发 OOM （Out of
						Memory）机制。</li>
				</ul>
				<h3 id="-">内存回收</h3>
				<h4 id="-">回收方式</h4>
				<p>如果没有空闲的物理内存，那么内核就会开始进行<strong>回收内存</strong>的工作，回收的方式主要是两种：直接内存回收和后台内存回收。</p>
				<ul>
					<li><strong>后台内存回收</strong>（kswapd）：在物理内存紧张的时候，会唤醒 kswapd
						内核线程来回收内存，这个回收内存的过程<strong>异步</strong>的，不会阻塞进程的执行。</li>
					<li><strong>直接内存回收</strong>（direct
						reclaim）：如果后台异步回收跟不上进程内存申请的速度，就会开始直接回收，这个回收内存的过程是<strong>同步</strong>的，会阻塞进程的执行。</li>
				</ul>
				<p>如果直接内存回收后，空闲的物理内存仍然无法满足此次物理内存的申请，那么内核就会<strong>触发 OOM （Out of Memory）机制</strong>。</p>
				<p>OOM Killer 机制会根据算法选择一个占用物理内存较高的进程，然后将其杀死，以便释放内存资源，如果物理内存依然不足，OOM Killer 会继续杀死占用物理内存较高的进程，直到释放足够的内存位置。
				</p>
				<p><strong>申请物理内存</strong>过程：</p>
				<p><img src="https://cdn.xiaolincoding.com//mysql/other/2f61b0822b3c4a359f99770231981b07.png"
						style="zoom:60%;" /></p>
				<h4 id="-"><strong>可以回收的内存</strong></h4>
				<ul>
					<li><strong>文件页</strong>（File-backed
						Page）：内核缓存的磁盘数据（Buffer）和内核缓存的文件数据（Cache）都叫作文件页。大部分文件页，都可以直接释放内存，以后有需要时，再从磁盘重新读取就可以了。而那些被应用程序修改过，并且暂时还没写入磁盘的数据（也就是脏页），就得先写入磁盘，然后才能进行内存释放。所以，<strong>回收干净页的方式是直接释放内存，回收脏页的方式是先写回磁盘后再释放内存</strong>。
					</li>
					<li><strong>匿名页</strong>（Anonymous
						Page）：这部分内存没有实际载体，不像文件缓存有硬盘文件这样一个载体，比如堆、栈数据等。这部分内存很可能还要再次被访问，所以不能直接释放内存，它们<strong>回收的方式是通过 Linux
							的 Swap 机制</strong>，Swap 会把不常访问的内存先写到磁盘中，然后释放这些内存，给其他更需要的进程使用。再次访问这些内存时，重新从磁盘读入内存就可以了。</li>
				</ul>
				<p>文件页与匿名页的回收都是基于LRU算法，也就是优先回收不常访问的内存。LRU算法，实际上维护着active和inactive两个双向链表。活跃页与不活跃页按照类型不同又分别分为文件页和匿名页。</p>
				<h4 id="-"><strong>回收内存带来的性能影响</strong></h4>
				<p>回收方式</p>
				<ul>
					<li>一种是后台内存回收，也就是唤醒 kswapd 内核线程，<strong>这种方式是异步回收的，不会阻塞进程</strong>。</li>
					<li>一种是直接内存回收，<strong>这种方式是同步回收的，会阻塞进程</strong>，这样就会造成很长时间的延迟，以及系统的 CPU 利用率会升高，最终引起系统负荷飙高。</li>
				</ul>
				<p>可被回收的内存类型有文件页和匿名页：</p>
				<ul>
					<li>文件页的回收：对于干净页是直接释放内存，这个操作不会影响性能，而对于脏页会先写回到磁盘再释放内存，这个操作会发生磁盘 I/O 的，这个操作是会影响系统性能的。</li>
					<li>匿名页的回收：如果开启了 Swap 机制，那么 Swap 机制会将不常访问的匿名页换出到磁盘中，下次访问时，再从磁盘换入到内存中，这个操作是会影响系统性能的。</li>
				</ul>
				<p><strong>解决：</strong></p>
				<ul>
					<li><strong>调整文件页与匿名页的回收倾向</strong>，Linux 提供了一个 <code>/proc/sys/vm/swappiness</code>
						选项，用来调整文件页和匿名页的回收倾向，一般建议 swappiness 设置为 0（默认值是
						60），这样在回收内存的时候，会<strong>更倾向于文件页的回收</strong>，但是并不代表不会回收匿名页。</li>
					<li><strong>尽早触发kswapd内核线程异步回收内存</strong>，内核定义了三个内存阈值：页最小阈值(pages_min)、页低阈值(pages_low)、页高阈值(pages_high)，剩余内存(pages_free)<strong>小于页低阈值(pages_low)</strong>，<strong>就会触发
							kswapd 进行后台回收（异步）</strong>，然后 kswapd
						会一直<strong>回收到剩余内存(pages_free)大于页高阈值(pages_high)</strong>。剩余内存<strong>小于最低阈值</strong>就会<strong>触发直接内存回收</strong>，应用程序就会被阻塞因为二者关系是同步的
					</li>
				</ul>
				<h4 id="-oom-">如何保护一个进程不被OOM杀掉</h4>
				<p>在 Linux 内核里有一个 <code>oom_badness()</code>
					函数，它会把系统中可以被杀掉的进程扫描一遍，并对每个进程打分，得分最高的进程就会被首先杀掉。<strong>用「系统总的可用页面数」乘以「OOM 校准值 oom_score_adj」再除以
						1000，最后再加上进程已经使用的物理页面数，计算出来的值越大，那么这个进程被OOM Kill的几率也就越大</strong>。</p>
				<ul>
					<li>如果你不想某个进程被首先杀掉，那你可以<strong>调整该进程的oom_score_adj</strong>，从而改变这个进程的得分结果，降低该进程被 OOM 杀死的概率。</li>
					<li>如果你想某个进程无论如何都不能被杀掉，那你可以将 oom_score_adj 配置为 -1000。</li>
				</ul>
				<p>但是，不建议将我们自己的业务程序的 oom_score_adj 设置为 -1000，因为业务程序一旦发生了内存泄漏，而它又不能被杀掉，这就会导致随着它的内存开销变大，OOM killer
					不停地被唤醒，从而把其他进程一个个给杀掉。</p>
				<h3 id="-swap-">内存交换--Swap机制</h3>
				<h4 id="-4g-8g-">在4g物理内存的机器上，申请8g内存会怎么样</h4>
				<p>应该考虑到的前置条件：</p>
				<ul>
					<li>操作系统是 32 位的，还是 64 位的？</li>
					<li>申请完 8G 内存后会不会被使用？</li>
					<li>操作系统有没有使用 Swap 机制？</li>
				</ul>
				<p><strong>32位系统</strong>：</p>
				<p>进程最多申请3g大小的虚拟内存空间，所以申请8g内存，申请阶段就会失败</p>
				<p><strong>64位系统</strong>：</p>
				<ul>
					<li>将Linux中的overcommit_memory参数置为1，如果为0，申请内存大于系统总内存就会失败</li>
					<li>开启swap机制<ul>
							<li>如果没有开启，就会出发OOM机制杀死进程（因为在申请内存的时候，虽然不访问就不会映射到物理内存，但是申请虚拟内存过程中还是用来物理内存，比如内核保存虚拟内存的数据结构，也占用物理内存，当物理内存不够就会开启OOM机制
							</li>
							<li>开启，是可以的。</li>
						</ul>
					</li>
				</ul>
				<h4 id="swap-">Swap机制</h4>
				<p>Linux 中的 Swap 机制会在内存不足和内存闲置的场景下触发：</p>
				<ul>
					<li><strong>内存不足</strong>：当系统需要的内存超过了可用的物理内存时，内核会将内存中不常使用的内存页交换到磁盘上为当前进程让出内存，保证正在执行的进程的可用性，这个内存回收的过程是<strong>强制的直接内存回收</strong>（Direct
						Page Reclaim）。<strong>直接内存回收是同步的过程，会阻塞当前申请内存的进程。</strong></li>
					<li><strong>内存闲置</strong>：应用程序在启动阶段使用的大量内存在启动后往往都不会使用，通过后台运行的守护进程（kSwapd），我们可以将这部分只使用一次的内存交换到磁盘上为其他内存的申请预留空间。kSwapd
						是 Linux 负责页面置换（Page
						replacement）的守护进程，它也是负责交换闲置内存的主要进程，它会在空闲内存低于一定水位时，回收内存页中的空闲内存保证系统中的其他进程可以尽快获得申请的内存。<strong>kSwapd
							是后台进程，所以回收内存的过程是异步的，不会阻塞当前申请内存的进程。</strong></li>
				</ul>
				<p>内核缓存的文件数据，因为都有对应的磁盘文件，所以在回收文件数据的时候， 直接写回到对应的文件就可以了。</p>
				<p><strong>但是像进程的堆、栈数据等，它们是没有实际载体，这部分内存被称为匿名页。</strong>而且这部分内存很可能还要再次被访问，所以不能直接释放内存，于是就需要有一个能保存匿名页的磁盘载体，这个载体就是
					Swap 分区。</p>
				<p>匿名页回收的方式是通过 Linux 的 Swap 机制，Swap 会把不常访问的内存先写到磁盘中，然后释放这些内存，给其他更需要的进程使用。再次访问这些内存时，重新从磁盘读入内存就可以了。</p>
				<p>如果<strong>物理内存足够大，那么可能不需要 Swap 机制</strong>，但是 Swap
					在这种情况下还是有一定<strong>优势</strong>：对于有发生内存泄漏几率的应用程序（进程），Swap
					交换分区更是重要，这可以确保内存泄露不至于导致物理内存不够用，最终导致系统崩溃。但内存泄露会引起频繁的 swap，此时非常影响操作系统的性能。</p>
				<p><strong>内存泄漏</strong>是指你向系统申请分配内存进行使用(new)，可是使用完了以后却不归还(delete)，结果你申请到的那块内存你自己也不能再访问（也许你把它的地址给弄丢了），而系统也不能再次将它分配给需要的程序。
				</p>
				<h4 id="-">需要注意的关键点</h4>
				<ol>
					<li>交换需要备份存储，通常是快速磁盘，它必须足够大，并且提供对这些内存映像的直接访问。</li>
					<li>为了有效使用CPU，需要每个进程的执行时间比交换时间长，而影响交换时间的主要是转移时间，转移时间与所交换的空间内存成正比。</li>
					<li>如果换出进程，比如确保该进程的内存空间成正比。</li>
					<li>交换空间通常作为磁盘的一整块，且独立于文件系统，因此使用就可能很快。</li>
					<li>交换通常在有许多进程运行且内存空间吃紧时开始启动，而系统负荷降低就暂停。</li>
					<li>普通交换使用不多，但交换的策略的某些变种在许多系统中（如UNIX系统）仍然发挥作用。</li>
				</ol>
				<h2 id="-">相关问题</h2>
				<h3 id="-">如何避免预读失效和缓存污染</h3>
				<ul>
					<li>Redis缓存淘汰算法是通过实现<strong>LFU算法</strong>避免的</li>
					<li>MySQL与Linux操作系统是通过改进<strong>LRU算法</strong>避免的</li>
				</ul>
				<p>Linux 操作系统是会对读取的文件数据进行缓存的，会缓存在文件系统中的 <strong>Page Cache</strong>。</p>
				<p>MySQL 的数据是存储在磁盘里的，为了提升数据库的读写性能，Innodb 存储引擎设计了一个<strong>缓冲池</strong>（Buffer Pool），Buffer Pool
					属于内存空间里的数据。（读取数据时优先在Buffer Pool中读取，没有才去磁盘。修改数据时，先修改Buffer Pool中数据页，然后将其设置为脏页，最后由后台线程将脏页写入磁盘）</p>
				<h4 id="-">预读失效</h4>
				<p>预读机制，本来要读0-3kb数据，但是磁盘基本读写单位是block（4kb），所以操作系统至少会读0-4kb，又考虑到靠近当前被访问的数据，在未来很大概率会被访问，所以会额外多申请几个page）</p>
				<p>这样做的好处是，<strong>减少了磁盘I/O次数，提高系统磁盘I/O吞吐量</strong>。</p>
				<p>预读失效带来的<strong>问题</strong></p>
				<ul>
					<li>提前加载的页，并没有被访问。但被访问的预读页却占用了LRU链表前排，而末尾淘汰页可能是热点数据，<strong>这样大大降低了缓存命中率</strong>。</li>
				</ul>
				<p><strong>如何避免</strong>（<strong>让预读页停留在内存里的时间要尽可能的短，让真正被访问的页才移动到 LRU
						链表的头部，从而保证真正被读取的热数据留在内存里的时间尽可能长</strong>。）</p>
				<ul>
					<li>Linux 操作系统实现两个了 LRU 链表：<strong>活跃 LRU 链表（active_list）和非活跃 LRU 链表（inactive_list）</strong>；<ul>
							<li><strong>预读页就只需要加入到 inactive list 区域的头部，当页被真正访问的时候，才将页插入 active list
									的头部</strong>。如果预读的页一直没有被访问，就会从 inactive list 移除，这样就不会影响 active list 中的热点数据。</li>
						</ul>
					</li>
					<li>MySQL 的 Innodb 存储引擎是在一个 LRU 链表上划分来 2 个区域：<strong>young 区域 和 old 区域</strong>。<ul>
							<li><strong>预读的页就只需要加入到 old 区域的头部，当页被真正访问的时候，才将页插入 young 区域的头部</strong>。</li>
						</ul>
					</li>
				</ul>
				<h4 id="-">缓存污染</h4>
				<p><strong>缓存污染：</strong>当我们在批量读取数据的时候，由于数据被访问了一次，这些大量数据都会被加入到「活跃 LRU 链表」里，然后之前缓存在活跃 LRU 链表（或者 young
					区域）里的热点数据全部都被淘汰了，<strong>如果这些大量的数据在很长一段时间都不会被访问的话，那么整个活跃 LRU 链表（或者 young 区域）就被污染了</strong>。</p>
				<p><strong>带来的问题</strong></p>
				<p>当某一个 SQL 语句<strong>扫描了大量的数据</strong>时，在 Buffer Pool 空间比较有限的情况下，可能会将 <strong>Buffer Pool
						里的所有页都替换出去，导致大量热数据被淘汰了</strong>，等这些热数据又被再次访问的时候，由于缓存未命中，就会产生大量的磁盘 I/O，MySQL 性能就会急剧下降。</p>
				<p><strong>避免影响</strong>（提高进入活跃LRU链表或者young区域的门槛）</p>
				<p>Linux 操作系统和 MySQL Innodb 存储引擎分别是这样提高门槛的：</p>
				<ul>
					<li><strong>Linux 操作系统</strong>：在内存页被访问<strong>第二次</strong>的时候，才将页从 inactive list 升级到 active list 里。
					</li>
					<li>MySQL Innodb：在内存页被访问第二次的时候，并不会马上将该页从 old 区域升级到 young 区域，因为还要进行停留在 old 区域的时间判断：<ul>
							<li>如果第二次的访问时间与第一次访问的时间<strong>在 1 秒内</strong>（默认值），那么该页就<strong>不会</strong>被从 old 区域升级到
								young 区域；</li>
							<li>如果第二次的访问时间与第一次访问的时间<strong>超过 1 秒</strong>，那么该页就<strong>会</strong>从 old 区域升级到 young 区域；
							</li>
						</ul>
					</li>
				</ul>
				<h3 id="-">覆盖与交换</h3>
				<ul>
					<li>由于程序运行时并非任何时候都要访问程序及数据的各个部分（尤其是大程序），因此可以把用户空间分成为一个固定区和若干个覆盖区。将<strong>经常活跃的部分放在固定区</strong>，其余部分按照调用关系分段，首先将那些<strong>即将要访问的段放入覆盖区</strong>，<strong>其他段放在外存中</strong>，在需要调用前，系统将其调入覆盖区，替换覆盖区中原有的段。
						<ul>
							<li>是<strong>打破了必须将一个进程的全部信息装入内存后才能运行的限制</strong>，<strong>但当同时运行程序的代码量大于主存时仍不能运行</strong>，再而，大家要注意到，内存中能够更新的地方只有覆盖区的段，不在覆盖区的段会常驻内存。
							</li>
						</ul>
					</li>
					<li>交换是指<strong>将系统暂时不用的程序或数据部分或全部从主存中调出</strong>，以腾出空间将系统要求使用的程序和数据调入主存，实际上是主存与外存之间不断的交换程序和数据，以实现用户在较小的存储空间中完成较多作业的执行。
						<ul>
							<li>内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)</li>
						</ul>
					</li>
				</ul>
				<p><strong>不同</strong>：</p>
				<p>一、结构不同
					1、覆盖：覆盖要求程序员给出程序段之间的覆盖结构。
					2、交换：交换不要求程序员给出程序段之间的交换结构。
					二、进行不同
					1、覆盖：覆盖主要在同一个作业或同一个进程内进行。
					2、交换：交换主要是在进程或作业之间进行</p>
				<h3 id="-">如何处理碎片文件</h3>
				<p>对于外部碎片，通过<strong>紧凑技术</strong>消除，就是操作系统不时地对进程进行移动和整理。但是这需要动态重定位寄存器地支持，且相对费时。紧凑地过程实际上类似于Windows系统中地磁盘整理程序，只不过后者是对外存空间地紧凑
				</p>
				<p>解决外部内存碎片的问题就是<strong>内存交换</strong>，<strong>回收内存时要尽可能地将相邻的空闲空间合并</strong>。</p>
				<h1 id="-">文件管理</h1>
				<h2 id="-">文件系统基础</h2>
				<h3 id="-">文件系统的基本组成</h3>
				<p>Linux 文件系统会为每个文件分配两个数据结构：<strong>索引节点（index node）和目录项（directory
						entry）</strong>，它们主要用来记录文件的元信息和目录层次结构。</p>
				<ul>
					<li>索引节点，也就是 <em>inode</em>，用来记录文件的元信息，比如 inode
						编号、文件大小、访问权限、创建时间、修改时间、<strong>数据在磁盘的位置</strong>等等。索引节点是文件的<strong>唯一</strong>标识，它们之间一一对应，也同样都会被存储在硬盘中，所以<strong>索引节点同样占用磁盘空间</strong>。
					</li>
					<li>目录项，也就是
						<em>dentry</em>，用来记录文件的名字、<strong>索引节点指针</strong>以及与其他目录项的层级关联关系。多个目录项关联起来，就会形成目录结构，但它与索引节点不同的是，<strong>目录项是由内核维护的一个数据结构，不存放于磁盘，而是缓存在内存</strong>。
					</li>
				</ul>
				<p><strong>注</strong>：目录是个文件，持久化存储在磁盘，而目录项是内核一个数据结构，缓存在内存。</p>
				<p>磁盘进行格式化的时候，会被分成三个存储区域，分别是超级块、索引节点区和数据块区。</p>
				<ul>
					<li><em>超级块</em>，用来存储文件系统的详细信息，比如块个数、块大小、空闲块等等。（当文件系统挂载时进入内存）</li>
					<li><em>索引节点区</em>，用来存储索引节点；（当文件被访问时进入内存）</li>
					<li><em>数据块区</em>，用来存储文件或目录数据；</li>
				</ul>
				<p>每个块组里有很多重复的信息，比如<strong>超级块和块组描述符表，这两个都是全局信息，而且非常的重要</strong>，这么做是有两个原因：</p>
				<ul>
					<li>如果系统崩溃破坏了超级块或块组描述符，有关文件系统结构和内容的所有信息都会丢失。如果有冗余的副本，该信息是可能恢复的。</li>
					<li>通过使文件和管理数据尽可能接近，减少了磁头寻道和旋转，这可以提高文件系统的性能。</li>
				</ul>
				<h3 id="-">虚拟文件系统</h3>
				<p>Linux 支持的文件系统也不少，根据存储位置的不同，可以把文件系统分为三类：</p>
				<ul>
					<li><em>磁盘的文件系统</em>，它是直接把数据存储在磁盘中，比如 Ext 2/3/4、XFS 等都是这类文件系统。</li>
					<li><em>内存的文件系统</em>，这类文件系统的数据不是存储在硬盘的，而是占用内存空间，我们经常用到的 <code>/proc</code> 和 <code>/sys</code>
						文件系统都属于这一类，读写这类文件，实际上是读写内核中相关的数据。</li>
					<li><em>网络的文件系统</em>，用来访问其他计算机主机数据的文件系统，比如 NFS、SMB 等等。</li>
				</ul>
				<h3 id="-">文件使用</h3>
				<p><img src="https://cdn.xiaolincoding.com/gh/xiaolincoder/ImageHost/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/%E6%96%87%E4%BB%B6%E7%B3%BB%E7%BB%9F/%E5%86%99%E5%88%B0%E7%A3%81%E7%9B%98%E8%BF%87%E7%A8%8B.png"
						style="zoom:67%;" /></p>
				<p>一般是：</p>
				<ul>
					<li>首先用 <code>open</code> 系统调用打开文件，<code>open</code> 的参数中包含文件的路径名和文件名。</li>
					<li>使用 <code>write</code> 写数据，其中 <code>write</code> 使用 <code>open</code>
						所返回的<strong>文件描述符</strong>，并不使用文件名作为参数。</li>
					<li>使用完文件后，要用 <code>close</code> 系统调用关闭文件，避免资源的泄露。</li>
				</ul>
				<p>文件描述符，是<strong>打开文件的标识</strong></p>
				<p>文件系统的基本操作单位是<strong>数据块</strong>。</p>
				<h3 id="-">文件储存方式</h3>
				<p><strong>针对已经被占用的数据块组织和管理</strong></p>
				<ul>
					<li>
						<p>连续空间存放方式</p>
						<ul>
							<li>优点，<strong>文件存放在磁盘「连续的」物理空间中</strong>文件的数据都是紧密相连，<strong>读写效率很高</strong></li>
							<li>缺点，1.磁盘碎片，当存入文件大于空缺空间 2.文件长大衣扩展不方便，想要扩大，需要用挪动的方式增加磁盘空间</li>
						</ul>
					</li>
					<li>
						<p>非连续空间存放方式</p>
						<ul>
							<li>链表，链表的方式存放是<strong>离散的，不用连续的</strong>，于是就可以<strong>消除磁盘碎片</strong>，可大大提高磁盘空间的利用率，同时<strong>文件的长度可以动态扩展</strong>。
								<ul>
									<li>隐式链表，<strong>实现的方式是文件头要包含「第一块」和「最后一块」的位置，并且每个数据块里面留出一个指针空间，用来存放下一个数据块的位置</strong>
										<ul>
											<li>缺点，<strong>无法直接访问数据块，只能通过指针顺序访问文件，以及数据块指针消耗了一定的存储空间</strong>。</li>
										</ul>
									</li>
									<li>显式链表，<strong>用于链接文件各数据块的指针，显式地存放在内存的一张链接表中</strong>，该表在整个磁盘仅设置一张，<strong>每个表项中存放链接指针，指向下一个数据块号</strong>。
										<ul>
											<li>优点，不仅显著地<strong>提高了检索速度</strong>，而且<strong>大大减少了访问磁盘的次数</strong></li>
											<li>缺点，<strong>不适用于大磁盘</strong></li>
										</ul>
									</li>
								</ul>
							</li>
							<li>
								<p>索引，是为每个文件创建一个「<strong>索引数据块</strong>」，里面存放的是<strong>指向文件数据块的指针列表</strong>，<strong>文件头需要包含指向「索引数据块」的指针</strong>
								</p>
								<ul>
									<li>文件的创建、增大、缩小很方便；</li>
									<li>不会有碎片的问题；</li>
									<li>支持顺序读写和随机读写；</li>
								</ul>
							</li>
							<li>
								<p>链式索引块，<strong>在索引数据块留出一个存放下一个索引数据块的指针</strong></p>
							</li>
							<li>多级索引块，<strong>通过一个索引块来存放多个索引数据块</strong></li>
						</ul>
					</li>
					<li>
						<p>Unix文件实现方式</p>
					</li>
				</ul>
				<p><img src="https://cdn.xiaolincoding.com/gh/xiaolincoder/ImageHost/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/%E6%96%87%E4%BB%B6%E7%B3%BB%E7%BB%9F/%E6%96%87%E4%BB%B6%E5%AD%98%E5%82%A8%E6%96%B9%E5%BC%8F%E6%AF%94%E8%BE%83.png"
						style="zoom:67%;" /></p>
				<p>它是根据文件的大小，存放的方式会有所变化：</p>
				<ul>
					<li>如果存放文件所需的数据块小于 10 块，则采用直接查找的方式；</li>
					<li>如果存放文件所需的数据块超过 10 块，则采用一级间接索引方式；</li>
					<li>如果前面两种方式都不够存放大文件，则采用二级间接索引方式；</li>
					<li>如果二级间接索引也不够存放大文件，这采用三级间接索引方式；</li>
				</ul>
				<p>优点：</p>
				<ul>
					<li>对于小文件使用直接查找的方式可减少索引数据块的开销；</li>
					<li>对于大文件则以多级索引的方式来支持，所以大文件在访问数据块时需要大量查询；</li>
				</ul>
				<h3 id="-">空闲空间管理</h3>
				<p><strong>保存一个数据块，我应该放在硬盘上的哪个位置</strong></p>
				<ul>
					<li>空闲表法，为所有空闲空间建立一张表，表内容包括空闲区的第一个块号和该空闲区的块个数<ul>
							<li>少量的空闲区时才有较好的效果,如果存储空间中有着大量的小的空闲区，则空闲表变得很大，这样查询效率会很低, <strong>适用于建立连续文件</strong>.</li>
						</ul>
					</li>
					<li>空闲链表法，使用「链表」的方式来管理空闲空间，每一个空闲块里有一个指针指向下一个空闲块<ul>
							<li>不适合用于大型文件系统</li>
						</ul>
					</li>
					<li>位图法，当值为 0 时，表示对应的盘块空闲，值为 1 时，表示对应的盘块已分配，<ul>
							<li>在 Linux 文件系统就采用了位图的方式来管理空闲空间，不仅用于数据空闲块的管理，还用于 inode 空闲块的管理，因为 inode 也是存储在磁盘的，自然也要有对其管理。
							</li>
						</ul>
					</li>
				</ul>
				<h3 id="-">目录存储</h3>
				<p>基于 Linux 一切皆文件的设计思想，目录其实也是个文件，你甚至可以通过 <code>vim</code> 打开它，它也有 inode，inode 里面也是指向一些块。</p>
				<p>最简单的保存格式就是<strong>列表</strong>，如果一个目录有超级多的文件，要想在这个目录下找文件，就得一项一项找，效率不高，适用可以把保存目录的格式改成<strong>哈希表</strong>，对文件名进行哈希计算，把哈希值保存起来。
				</p>
				<p><strong>普通文件的块里面保存的是文件数据，而目录文件的块里面保存的是目录里面一项一项的文件信息。</strong></p>
				<h3 id="-">软硬链接</h3>
				<ul>
					<li>硬链接<ul>
							<li>硬链接是<strong>多个目录项中的「索引节点」指向一个文件</strong>，也就是指向同一个inode。但inode不可能跨越文件系统，每个文件系统都有各自的inode数据结构和列表，所以<strong>硬链接不可用于跨文件系统</strong>。
							</li>
							<li>由于多个目录项都是指向一个 inode，那么<strong>只有删除文件的所有硬链接以及源文件时，系统才会彻底删除该文件。</strong></li>
						</ul>
					</li>
					<li>软链接，重新创建一个文件，这个文件有<strong>独立的 inode</strong>，但是这个<strong>文件的内容是另外一个文件的路径</strong>
						<ul>
							<li>访问软链接的时候，实际上相当于访问到了另外一个文件，所以<strong>软链接是可以跨文件系统的</strong></li>
							<li><strong>目标文件被删除了，链接文件还是在的，只不过指向的文件找不到了</strong></li>
						</ul>
					</li>
				</ul>
				<h2 id="-">磁盘组织与管理</h2>
				<h3 id="page-cache">Page Cache</h3>
				<p>当磁盘写文件时，写一半的时候如果进程崩溃了，已写入的数据不会丢失。</p>
				<p><strong>原因</strong>：因为进程在执行 write （使用缓冲 IO）系统调用的时候，实际上是<strong>将文件数据写到了内核的 page
						cache</strong>，它是文件系统中用于缓存文件数据的缓冲，所以即使进程崩溃了，文件数据还是保留在内核的 page cache，我们读数据的时候，也是从内核的 page cache
					读取，因此还是依然读的进程崩溃前写入的数据。然后内核会找个合适的时机，将page cache中的数据持久化到磁盘。但是如果 page cache
					里的文件数据，在持久化到磁盘化到磁盘之前，系统发生了崩溃，那这部分数据就会丢失了。可以在程序里<strong>调用fsync函数</strong>，在写文件的时候，立刻将文件数据持久化到磁盘，这样就可以解决系统崩溃导致的文件数据丢失的问题。
				</p>
				<p>当前 Linux 下以两种方式实现文件一致性（数据一致+元数据一致）：</p>
				<ol>
					<li><strong>Write Through（写穿）</strong>：向用户层提供特定接口，应用程序可主动调用接口来保证文件一致性；</li>
					<li><strong>Write back（写回）</strong>：系统中存在定期任务（表现形式为内核线程），周期性地同步文件系统中文件脏数据块，这是默认的 Linux 一致性方案；</li>
				</ol>
				<p>Write Through 与 Write back 在持久化的可靠性上有所不同：</p>
				<ul>
					<li>Write Through 以牺牲系统 I/O 吞吐量作为代价，向上层应用确保一旦写入，数据就已经落盘，不会丢失；</li>
					<li>
						<p>Write back 在系统发生宕机的情况下无法确保数据已经落盘，因此存在数据丢失的问题。不过，在程序挂了，例如被 kill -9，Page Cache 中的数据操作系统还是会确保落盘；
						</p>
						<p><strong>Page Cache 的本质是由 Linux 内核管理的内存区域。我们通过 mmap 以及 buffered I/O 将文件读取到内存空间实际上都是读取到 Page
								Cache 中。</strong></p>
					</li>
				</ul>
				<p>page 是内存管理分配的基本单位， Page Cache 由多个 page 构成。</p>
				<p>Page Cache 与 buffer cache：</p>
				<ul>
					<li>Page cache 用于缓存文件的页数据，页是逻辑上的概念，因此 Page Cache 是与文件系统同级的；</li>
					<li>buffer cache 用于缓存块设备(如磁盘)的块数据，块是物理上的概念，因此 buffer cache 是与块设备驱动程序同级的。</li>
				</ul>
				<p>Page Cache 与 buffer cache 的<strong>共同目的都是加速数据 I/O</strong>：</p>
				<ul>
					<li>写数据时首先写到缓存，将写入的页标记为 dirty，然后向外部存储 flush，也就是缓存写机制中的 write-back（另一种是 write-through，Linux
						默认情况下不采用）；</li>
					<li>读数据时首先读取缓存，如果未命中，再去外部存储读取，并且将读取来的数据也加入缓存。操作系统总是积极地将所有空闲内存都用作 Page Cache 和 buffer
						cache，当内存不够用时也会用 LRU 等算法淘汰缓存页</li>
				</ul>
				<p><strong>Page cache优缺点</strong></p>
				<p>优点：</p>
				<ul>
					<li>加快数据访问。如果内存中有缓存，下次访问直接命中缓存就行，内存访问比磁盘访问快。</li>
					<li>减少I/O次数。提高系统磁盘I/O吞吐量。Page cache的缓存与预读能力。</li>
				</ul>
				<p>缺点：</p>
				<ul>
					<li>占用额外物理内存空间，物理内存在比较紧俏的时候可能会导致频繁的 swap 操作，最终导致系统的磁盘 I/O 负载的上升。</li>
					<li>对应用层并没有提供很好的管理 API，几乎是透明管理。</li>
					<li>在某些应用场景下比 Direct I/O 多一次磁盘读 I/O 以及磁盘写 I/O。（其他所有技术中，数据至少需要在内核空间存储一份，但是在 Direct I/O
						技术中，数据直接存储在用户空间中，此时用户空间直接通过 DMA 的方式与磁盘以及网卡进行数据拷贝，绕过了内核。）<ul>
							<li>缓存文件 I/O：用户空间要读写一个文件并<strong>不直接</strong>与磁盘交互，而是中间夹了一层缓存，即 page cache；</li>
							<li>直接文件 I/O：用户空间读取的文件<strong>直接</strong>与磁盘交互，没有中间 page cache 层；</li>
						</ul>
					</li>
				</ul>
				<p><strong>大文件传输用什么方式实现</strong></p>
				<p><strong>在高并发的场景下，针对大文件的传输的方式，应该使用「异步 I/O + 直接 I/O」来替代零拷贝技术</strong></p>
				<p>直接 I/O 应用场景常见的两种：</p>
				<ul>
					<li>应用程序已经实现了磁盘数据的缓存，那么可以不需要 PageCache 再次缓存，减少额外的性能损耗。在 MySQL 数据库中，可以通过参数设置开启直接 I/O，默认是不开启；</li>
					<li>传输大文件的时候，由于大文件难以命中 PageCache 缓存，而且会占满 PageCache 导致「热点」文件无法充分利用缓存，从而增大了性能开销，因此，这时应该使用直接 I/O。</li>
				</ul>
				<p>另外，由于直接 I/O 绕过了 PageCache，就无法享受内核的这两点的优化：</p>
				<ul>
					<li>内核的 I/O 调度算法会缓存尽可能多的 I/O 请求在 PageCache 中，最后「<strong>合并</strong>」成一个更大的 I/O
						请求再发给磁盘，这样做是为了减少磁盘的寻址操作；</li>
					<li>内核也会「<strong>预读</strong>」后续的 I/O 请求放在 PageCache 中，一样是为了减少对磁盘的操作；</li>
				</ul>
				<p>所以，传输文件的时候，我们要根据文件的大小来使用不同的方式：</p>
				<ul>
					<li>传输大文件的时候，使用<strong>「异步 I/O + 直接 I/O」</strong>；</li>
					<li>传输小文件的时候，则使用「零拷贝技术」；</li>
				</ul>
				<h3 id="-">磁盘调度算法</h3>
				<p><strong>读写一个磁盘块的时间的影响因素</strong>有：</p>
				<ul>
					<li>旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）</li>
					<li>寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）</li>
					<li>实际的数据传输时间</li>
				</ul>
				<p>其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短</p>
				<table>
					<thead>
						<tr>
							<th>算法</th>
							<th>描述</th>
							<th>优点</th>
							<th>缺点</th>
						</tr>
					</thead>
					<tbody>
						<tr>
							<td>先来先服务</td>
							<td>先到来的请求，先被服务</td>
							<td>公平简单</td>
							<td>平均寻道时间较长</td>
						</tr>
						<tr>
							<td>最短寻道时间优先</td>
							<td>优先调度与当前磁头所在磁道距离最近的磁道</td>
							<td>平均寻道时间比较低，</td>
							<td>不公平，两端磁道请求容易出现饥饿现象</td>
						</tr>
						<tr>
							<td>扫描算法SCAN</td>
							<td>磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向</td>
							<td>不会产生饥饿</td>
							<td>中间部分相比于其他部分响应频率高</td>
						</tr>
						<tr>
							<td>循环扫描算法C-SCAN</td>
							<td>磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且<strong>返回中途不处理任何请求</strong>，该算法的特点，就是<strong>磁道只响应一个方向上的请求</strong>。
							</td>
							<td>磁道响应频率比较平均</td>
							<td></td>
						</tr>
						<tr>
							<td>LOOK 与 C-LOOK算法</td>
							<td><strong>磁头在移动到「最远的请求」位置，然后立即反向移动</strong></td>
							<td></td>
						</tr>
					</tbody>
				</table>
				<h1 id="-">网络系统</h1>
				<h2 id="-">零拷贝</h2>
				<p><strong>零拷贝（*Zero-copy*）技术，没有在内存层面去拷贝数据，也就是说全程没有通过 CPU 来搬运数据，所有的数据都是通过 DMA 来进行传输的。</strong></p>
				<p><img src="https://cdn.xiaolincoding.com/gh/xiaolincoder/ImageHost2/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/%E9%9B%B6%E6%8B%B7%E8%B4%9D/%E4%BC%A0%E7%BB%9F%E6%96%87%E4%BB%B6%E4%BC%A0%E8%BE%93.png"
						style="zoom:67%;" /></p>
				<p><strong>传统的文件传输</strong></p>
				<ul>
					<li>发生了四次用户态与内核态的上下文切换。两次系统调用，一次是 <code>read()</code> ，一次是 <code>write()</code>。每次系统调用会发生两次上下文切换。
					</li>
					<li>发生了4次数据拷贝。两次 DMA 的拷贝，两次通过 CPU 拷贝。<ul>
							<li><em>第一次拷贝</em>，把磁盘上的数据拷贝到操作系统内核的缓冲区里，这个拷贝的过程是通过 DMA 搬运的。</li>
							<li><em>第二次拷贝</em>，把内核缓冲区的数据拷贝到用户的缓冲区里，于是我们应用程序就可以使用这部分数据了，这个拷贝到过程是由 CPU 完成的。</li>
							<li><em>第三次拷贝</em>，把刚才拷贝到用户的缓冲区里的数据，再拷贝到内核的 socket 的缓冲区里，这个过程依然还是由 CPU 搬运的。</li>
							<li><em>第四次拷贝</em>，把内核的 socket 缓冲区里的数据，拷贝到网卡的缓冲区里，这个过程又是由 DMA 搬运的。</li>
						</ul>
					</li>
				</ul>
				<p><strong>优化文件传输性能</strong></p>
				<ul>
					<li>减少系统调用次数，</li>
					<li>减少数据拷贝(用户缓冲区没必要存在)，从内核的读缓冲区拷贝到用户的缓冲区里，再从用户的缓冲区里拷贝到 socket 的缓冲区里，在用户空间我们并不会对数据。<ul>
							<li>mmap + write。<code>mmap()</code>
								系统调用函数会直接把内核缓冲区里的数据「<strong>映射</strong>」到用户空间，这样，操作系统内核与用户空间就不需要再进行任何的数据拷贝操作。<strong>（减少一次数据拷贝）</strong>
								<ul>
									<li>应用进程调用了 <code>mmap()</code> 后，DMA 会把磁盘的数据拷贝到内核的缓冲区里。接着，应用进程跟操作系统内核「共享」这个缓冲区；
									</li>
									<li>应用进程再调用 <code>write()</code>，操作系统直接将内核缓冲区的数据拷贝到 socket 缓冲区中，这一切都发生在内核态，由 CPU
										来搬运数据；</li>
									<li>最后，把内核的 socket 缓冲区里的数据，拷贝到网卡的缓冲区里，这个过程是由 DMA 搬运的。</li>
								</ul>
							</li>
							<li>sendfile，替代 <code>read()</code> 和 <code>write()</code> 这两个系统调用，这样就可以减少一次系统调用，也就减少了 2
								次上下文切换的开销。其次，该系统调用，可以直接把内核缓冲区里的数据拷贝到 socket 缓冲区里，不再拷贝到用户态，这样就只有 2 次上下文切换，和 3 次数据拷贝。<ul>
									<li>第一步，通过 DMA 将磁盘上的数据拷贝到内核缓冲区里；</li>
									<li>第二步，缓冲区描述符和数据长度传到 socket 缓冲区，<strong>这样网卡的 SG-DMA
											控制器</strong>就可以直接将内核缓存中的数据拷贝到网卡的缓冲区里，此过程不需要将数据从操作系统内核缓冲区拷贝到 socket
										缓冲区中，这样就减少了一次数据拷贝；</li>
								</ul>
							</li>
						</ul>
					</li>
				</ul>
				<p><img src="https://cdn.xiaolincoding.com/gh/xiaolincoder/ImageHost2/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F/%E9%9B%B6%E6%8B%B7%E8%B4%9D/senfile-%E9%9B%B6%E6%8B%B7%E8%B4%9D.png"
						style="zoom:67%;" /></p>
				<h2 id="i-o">I/O</h2>
				<h3 id="i-o-">I/O分类</h3>
				<p><strong>缓冲I/O与非缓冲I/O</strong>，是否利用标准库缓冲</p>
				<ul>
					<li>缓冲 I/O，利用的是标准库的缓存实现文件的加速访问，而标准库再通过系统调用访问文件。</li>
					<li>非缓冲 I/O，直接通过系统调用访问文件，不经过标准库缓存。</li>
				</ul>
				<p><strong>直接I/O与非直接I/O</strong>，是否利用操作系统缓存</p>
				<ul>
					<li>直接 I/O，不会发生内核缓存和用户程序之间数据复制，而是直接经过文件系统访问磁盘。</li>
					<li>非直接 I/O，读操作时，数据从内核缓存中拷贝给用户程序，写操作时，数据从用户程序拷贝给内核缓存，再由内核决定什么时候写入数据到磁盘。</li>
				</ul>
				<p>发生场景（内存比较紧张）：</p>
				<ul>
					<li>在调用 <code>write</code> 的最后，当发现内核缓存的数据太多的时候，内核会把数据写到磁盘上；</li>
					<li>用户主动调用 <code>sync</code>，内核缓存会刷到磁盘上；</li>
					<li>当内存十分紧张，无法再分配页面时，也会把内核缓存的数据刷到磁盘上；</li>
					<li>内核缓存的数据的缓存时间超过某个时间时，也会把数据刷到磁盘上；</li>
				</ul>
				<p><strong>同步与异步I/O</strong></p>
				<p>I/O 是分为两个过程的：</p>
				<ol>
					<li>数据准备的过程</li>
					<li>
						<p>数据从内核空间拷贝到用户进程缓冲区的过程</p>
					</li>
					<li>
						<p>同步I/O</p>
						<ul>
							<li>阻塞I/O<strong>(过程1,2都阻塞)</strong>，用户程序执行 <code>read</code>
								，<strong>线程会被阻塞，一直等到内核数据准备好，并把数据从内核缓冲区拷贝到应用程序的缓冲区中</strong>，当拷贝过程完成，<code>read</code>
								才会返回。</li>
							<li>非阻塞I/O<strong>(只阻塞过程2)</strong>，非阻塞的 read
								请求在数据未准备好的情况下立即返回，此时<strong>应用程序不断轮询内核</strong>，直到数据准备好，内核将数据拷贝到应用程序缓冲区，<code>read</code>
								调用才可以获取到结果。</li>
							<li>非阻塞I/O的多路复用<strong>(只阻塞过程2)</strong>，如果没有事件发生，那么当前线程就会发生阻塞，这时 CPU
								会切换其他线程执行任务，等内核发现有事件到来的时候，会唤醒阻塞在 I/O 多路复用接口的线程，然后用户可以进行后续的事件处理<ul>
									<li><strong>I/O 多路复用接口最大的优势在于，用户可以在一个线程内同时处理多个 socket 的 IO 请求</strong></li>
								</ul>
							</li>
						</ul>
					</li>
					<li>异步I/O<strong>(过程1,2都不阻塞)</strong></li>
				</ol>
				<h3 id="i-o-">I/O多路复用</h3>
				<h4 id="-">多进程模型</h4>
				<p>服务器的主进程负责监听客户的连接，一旦与客户端连接完成，accept() 函数就会返回一个「已连接 Socket」，这时就通过 <code>fork()</code>
					函数创建一个子进程，实际上就把父进程所有相关的东西都<strong>复制</strong>一份，包括<strong>文件描述符、内存地址空间、程序计数器、执行的代码</strong>等，但是会根据<strong>返回值</strong>来区分是父进程还是子进程，如果返回值是
					0，则是子进程；如果返回值是其他的整数，就是父进程。</p>
				<ul>
					<li>父进程，监听Socket</li>
					<li>子进程，关心已连接的Socket</li>
				</ul>
				<p>注：</p>
				<ul>
					<li>孤儿进程，父进程退出，子进程还在运行，孤儿进程会被init进程收养</li>
					<li>僵尸进程，子进程退出(利用exit结束自己的生命周期)，父进程没有调用wait或waitpid获取子进程状态，那么子进程的文件描述符仍然保存在子系统<ul>
							<li>危害，1.资源泄漏（资源没有完全释放） 2.新的进程无法创建（操作系统所创建的最大进程数量是有限的）</li>
							<li>处理，子进程退出时<strong>向父进程发送SIGCHILD信号</strong>，父进程处理SIGCHILD信号。在信号处理函数中<strong>调用wait</strong>进行处理僵尸进程。
							</li>
							<li>避免。<ul>
									<li>通过signal(SIGCHLD, SIG_IGN)通知内核对子进程的结束不关心，由内核回收。</li>
									<li>父进程调用wait/waitpid等函数等待子进程结束，如果尚无子进程退出wait会导致父进程阻塞。waitpid可以通过传递WNOHANG使父进程不阻塞立即返回。
									</li>
									<li>如果父进程很忙可以用signal注册信号处理函数，在信号处理函数调用wait/waitpid等待子进程退出。</li>
									<li>通过两次调用fork。父进程首先调用fork创建一个子进程然后waitpid等待子进程退出，子进程再fork一个孙进程后退出。</li>
								</ul>
							</li>
						</ul>
					</li>
					<li>守护进程，是运行在后台的一种特殊进程。它独立于控制终端并且周期性地执行某种任务或等待处理某些发生的事件。</li>
				</ul>
				<h4 id="-">多线程模型</h4>
				<p>同进程里的线程可以共享进程的部分资源，比如<strong>文件描述符列表、进程空间、代码、全局数据、堆、共享库</strong>等，这些共享些资源在上下文切换时不需要切换，而只需要切换<strong>线程的私有数据、寄存器等不共享的数据</strong>。
				</p>
				<p>可以使用<strong>线程池</strong>的方式来避免线程的频繁创建和销毁。</p>
				<p>线程池，提前创建若干个线程，当新连接建立时，将这个已连接的 Socket 放入到一个队列里，然后线程池里的线程负责从队列中取出「已连接 Socket 」进行处理。</p>
				<h4 id="i-o-select-poll">I/O多路复用--select/poll</h4>
				<p>使用I/O多路复用，<strong>进程可以通过一个系统调用函数从内核中获取多个事件</strong>。</p>
				<ul>
					<li>select/poll<ul>
							<li>方式，将已连接的 Socket 都放到一个<strong>文件描述符集合</strong>，然后调用 select
								函数将文件描述符集合<strong>拷贝</strong>到内核里，让内核来检查是否有网络事件产生，检查的方式很粗暴，就是通过<strong>遍历</strong>文件描述符集合的方式，当检查到有事件产生后，将此
								Socket 标记为可读或可写，
								接着再把整个文件描述符集合<strong>拷贝</strong>回用户态里，然后用户态还需要再通过<strong>遍历</strong>的方法找到可读或可写的
								Socket，然后再对其处理。（两次拷贝，两次遍历）</li>
							<li>select 使用固定长度的
								BitsMap，表示文件描述符集合，而且所支持的文件描述符的个数是有限制的。而poll利用动态数组，以链表形式组织，突破了select的文件描述符个数限制，当然还是会受系统文件描述符限制。
							</li>
							<li><strong>相同点</strong>，<strong>使用「线性结构」存储进程关注的 Socket 集合，因此都需要遍历文件描述符集合来找到可读或可写的
									Socket，时间复杂度为 O(n)，而且也需要在用户态与内核态之间拷贝文件描述符集合</strong>，这种方式随着并发数上来，性能的损耗会呈指数级增长。</li>
						</ul>
					</li>
					<li>缺陷，当客户端越多，也就是 Socket 集合越大，Socket 集合的遍历和拷贝会带来很大的开销，因此也很难应对 C10K。</li>
				</ul>
				<h4 id="i-o-epoll">I/O多路复用--epoll</h4>
				<ul>
					<li>epoll<ul>
							<li><em>第一点</em>，epoll 在内核里使用<strong>红黑树来跟踪进程所有待检测的文件描述字</strong>，把需要监控的 socket 通过
								<code>epoll_ctl()</code> 函数加入内核中的红黑树里，红黑树是个高效的数据结构，增删改一般时间复杂度是 <code>O(logn)</code>。而
								select/poll 内核里没有类似 epoll 红黑树这种保存所有待检测的 socket 的数据结构，所以 select/poll 每次操作时都传入整个 socket
								集合给内核，而 epoll 因为在内核维护了红黑树，可以保存所有待检测的 socket ，所以只需要传入一个待检测的
								socket，减少了内核和用户空间大量的数据拷贝和内存分配。</li>
							<li><em>第二点</em>， epoll 使用<strong>事件驱动</strong>的机制，内核里<strong>维护了一个链表来记录就绪事件</strong>，当某个
								socket 有事件发生时，通过<strong>回调函数</strong>内核会将其加入到这个就绪事件列表中，当用户调用 <code>epoll_wait()</code>
								函数时，只会返回有事件发生的文件描述符的个数，不需要像 select/poll 那样轮询扫描整个 socket 集合，大大提高了检测的效率。</li>
						</ul>
					</li>
				</ul>
				<p><strong>事件触发模式</strong></p>
				<ul>
					<li>边缘触发，当被监控的 Socket 描述符上有可读事件发生时，<strong>服务器端只会从 epoll_wait 中苏醒一次</strong>，即使进程没有调用 read
						函数从内核读取数据，也依然只苏醒一次，因此我们程序要保证一次性将内核缓冲区的数据读取完；（只叫一次）</li>
					<li>水平触发，当被监控的 Socket 上有可读事件发生时，<strong>服务器端不断地从 epoll_wait 中苏醒，直到内核缓冲区数据被 read
							函数读完才结束</strong>，目的是告诉我们有数据需要读取；（叫很多次，直至数据读完，select/poll都是这种）</li>
					<li>边缘触发使用效率高，可以加您少epoll_wait的系统调用次数。系统调用是有一定开销的，因为存在上下文切换。</li>
				</ul>
				<p><strong>注</strong>：<strong>多路复用 API 返回的事件并不一定可读写的</strong>，如果使用阻塞 I/O， 那么在调用 read/write
					时则会发生程序阻塞，因此最好搭配非阻塞 I/O，以便应对极少数的特殊情况。</p>
				<h2 id="-">网络模式</h2>
				<h3 id="reactor-">Reactor模式</h3>
				<p><strong>要求主线程（I/O处理单元）只负责监听文件描述符上是否有事件发生</strong>，有的话就立即将该事件通知工作线程（逻辑单元），将 socket
					可读可写事件放入请求队列，交给工作线程处理。除此之外，主线程不做任何其他实质性的工作。读写数据，接受新的连接，以及处理客户请求均在工作线程中完成。
					使用同步 I/O（以 epoll_wait 为例）实现的 Reactor 模式的工作流程是：</p>
				<ol>
					<li>主线程往 epoll内核事件表中注册 socket上的读就绪事件。</li>
					<li>主线程调用epoll_wait等待 socket上有数据可读。</li>
					<li>当socket上有数据可读时，epoll_wait通知主线程。主线程则将socket可读事件放入请求队列。</li>
					<li>睡眠在请求队列上的某个工作线程被唤醒，它从 socket 读取数据，并处理客户请求，然后往epoll内核事件表中注册该socket上的写就绪事件。</li>
					<li>当主线程调用 epoll_wait 等待socket可写。</li>
					<li>当 socket 可写时，epoll_wait通知主线程。主线程将 socket 可写事件放入请求队列。</li>
					<li>睡眠在请求队列上的某个工作线程被唤醒，它往 socket 上写入服务器处理客户请求的结果。</li>
				</ol>
				<p><strong>包含</strong></p>
				<p>单 Reactor 单进程 / 线程，</p>
				<ul>
					<li>第一个缺点，因为只有一个进程，<strong>无法充分利用 多核 CPU 的性能</strong>；</li>
					<li>第二个缺点，Handler 对象在业务处理时，整个进程是无法处理其他连接的事件的，<strong>如果业务处理耗时比较长，那么就造成响应的延迟</strong>；</li>
				</ul>
				<p>单 Reactor 多线程 / 多进程</p>
				<p>优势在于<strong>能够充分利用多核 CPU 的性能</strong>，多线程需要共享资源，则需要加锁</p>
				<p>单Reactor</p>
				<p>1.考虑并发问题</p>
				<p>2.<strong>因为一个 Reactor 对象承担所有事件的监听和响应，而且只在主线程中运行，在面对瞬间高并发的场景时，容易成为性能的瓶颈的地方</strong>。</p>
				<p>多 Reactor 多进程 / 线程</p>
				<ul>
					<li>主线程和子线程分工明确，主线程只负责接收新连接，子线程负责完成后续的业务处理。</li>
					<li>主线程和子线程的交互很简单，主线程只需要把新连接传给子线程，子线程无须返回数据，直接就可以在子线程将处理结果发送给客户端。</li>
				</ul>
				<h3 id="proactor-">Proactor模式</h3>
				<p>Proactor 模式<strong>将所有 I/O 操作都交给主线程和内核来处理（进行读、写）</strong>，工作线程仅仅负责业务逻辑。使用异步 I/O 模型（以 aio_read 和
					aio_write 为例）实现的 Proactor 模式的工作流程是：</p>
				<ol>
					<li>主线程调用aio_read函数向内核注册socket上的读完成事件，并告诉内核用户读缓冲区的位置，以及读操作完成时如何通知应用程序（这里以信号为例）。</li>
					<li>主线程继续处理其他逻辑。</li>
					<li>当socket上的数据被读入用户缓冲区后，内核将向应用程序发送一个信号，以通知应用程序数据已经可用。</li>
					<li>应用程序预先定义好的信号处理函数选择一个工作线程来处理客户请求。工作线程处理完客户请求后，调用 aio_write 函数向内核注册 socket
						上的写完成事件，并告诉内核用户写缓冲区的位置，以及写操作完成时如何通知应用程序。</li>
					<li>主线程继续处理其他逻辑。</li>
					<li>当用户缓冲区的数据被写入 socket 之后，内核将向应用程序发送一个信号，以通知应用程序数据已经发送完毕。</li>
					<li>应用程序预先定义好的信号处理函数选择一个工作线程来做善后处理，比如决定是否关闭 socket。</li>
				</ol>
				<h3 id="-proactor-">模拟Proactor模式</h3>
				<p>使用同步 I/O 方式模拟出 Proactor
					模式。原理是：主线程执行数据读写操作，读写完成之后，主线程向工作线程通知这一”完成事件“。那么从工作线程的角度来看，它们就直接获得了数据读写的结果，接下来要做的只是对读写的结果进行逻辑处理。
					使用同步 I/O 模型（以 epoll_wait为例）模拟出的 Proactor 模式的工作流程如下：</p>
				<ol>
					<li>主线程往 epoll 内核事件表中注册 socket 上的读就绪事件。</li>
					<li>主线程调用 epoll_wait 等待 socket 上有数据可读。</li>
					<li>当 socket 上有数据可读时，epoll_wait 通知主线程。主线程从 socket 循环读取数据，直到没有更多数据可读，然后将读取到的数据封装成一个请求对象并插入请求队列。</li>
					<li>睡眠在请求队列上的某个工作线程被唤醒，它获得请求对象并处理客户请求，然后往 epoll 内核事件表中注册 socket 上的写就绪事件。</li>
					<li>主线程调用 epoll_wait 等待 socket 可写。</li>
					<li>当 socket 可写时，epoll_wait 通知主线程。主线程往 socket 上写入服务器处理客户请求的结果。</li>
				</ol>
				<h3 id="-">总结</h3>
				<ul>
					<li>Reactor，<strong>非阻塞同步网络模式，感知就绪可读写事件</strong>。在每次感知到有事件发生（比如可读就绪事件）后，就需要应用进程主动调用 read
						方法来完成数据的读取，也就是要应用进程主动将 socket 接收缓存中的数据读到应用进程内存中，这个过程是同步的，读取完数据后应用进程才能处理数据。</li>
					<li>Proactor，<strong>异步网络模式，感知已完成读写事件</strong>。在发起异步读写请求时，需要传入数据缓冲区的地址（用来存放结果数据）等信息，这样系统内核才可以自动帮我们把数据的读写工作完成，这里的读写工作全程由操作系统来做，并不需要像
						Reactor 那样还需要应用进程主动发起 read/write 来读写数据，操作系统完成读写工作后，就会通知应用进程直接处理数据。</li>
				</ul>
				<h2 id="-">一致性哈希</h2>
				<p>针对多台服务器构成的集群，当每个服务器存储的数据都是相同的，当每次读数据的请求时，可以使用<strong>轮询</strong>来分配请求。考虑到每个服务器的硬件配置不同，<strong>引入权重值</strong>，按照一定比重分配在不同服务器上，让硬件配置好的服务器承担更多的请求----加权轮询。缺点：针对<strong>分布式系统（数据分片的系统，会将数据水平切分到不同的节点来存储，也就是将数据分布到了不同的节点），因为每个服务器存储的数据不同</strong>，加权轮询的方式无法应对。
				</p>
				<p>哈希算法：进行取模运算来解决分布式系统的负载均衡算法。比如分布式系统中有 3 个节点，基于 <code>hash(key) % 3</code>
					公式对数据进行了映射。缺点：<strong>如果服务器的数量发生变换，也就是对系统做扩容或者缩容时，必须迁移改变了映射关系的数据，重新映射</strong>，否则会出现查询不到数据的问题。但是有时候迁移成本很高。
				</p>
				<p><strong>一致性哈希算法</strong>：也用了取模运算，但与哈希算法不同的是，<strong>是对 2^32 进行取模运算，是一个固定的值</strong>。可以认为对 2^32
					进行取模运算的结果值组织成一个圆环，称为<strong>哈希环</strong>。<strong>在一致哈希算法中，如果增加或者移除一个节点，仅影响该节点在哈希环上顺时针相邻的后继节点，其它数据也不会受到影响</strong>。
				</p>
				<p>一致性哈希要做两步哈希：</p>
				<ul>
					<li>对每个服务器进行哈希计算，做哈希映射，比如根据服务器的IP地址进行哈希；</li>
					<li>对数据就绪存储或访问时，对数据进行哈希映射。</li>
				</ul>
				<p><strong>存在问题：</strong></p>
				<p><strong>一致性哈希算法并不保证节点能够在哈希环上分布均匀</strong>，这样就会带来一个问题，会有<strong>大量的请求集中在一个节点</strong>上。一旦该节点被移除（宕机），根据一致性哈希算法，该节点的数据全部迁移到右相邻服务器上，导致该服务器数据量和访问量都会迅速增加很多倍，超过服务器的处理能力上限后，会导致该服务器崩溃，进而形成雪崩式的连锁反应。
				</p>
				<p><strong>改进：</strong></p>
				<p>具体做法是，<strong>不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系。</strong></p>
				<p>虚拟节点作用：</p>
				<ul>
					<li>提高节点均衡度。<strong>不再将真实节点映射到哈希环上，而是将虚拟节点映射到哈希环上，并将虚拟节点映射到实际节点，所以这里有「两层」映射关系</strong>。<strong>节点数量多了后，节点在哈希环上的分布就相对均匀了</strong>。
					</li>
					<li>稳定性更高。<strong>当节点变化时，会有不同的节点共同分担系统的变化</strong></li>
				</ul>
				<h1 id="-">其他知识</h1>
				<ul>
					<li>操作系统特征。</li>
				</ul>
				<p>并发，共享，虚拟，异步</p>

			</article>
		</div>
</body>
</html>